การค้นหาเชิงเส้นใน Python
Linear search ใช้ได้แม้ข้อมูลยังไม่เรียง
การค้นหาแบบเชิงเส้นคืออะไร?
การค้นหาแบบเชิงเส้นตรวจสอบสมาชิกทีละตัวจากต้นรายการจนพบค่าเป้าหมายหรือถึงท้ายรายการ โดยไม่จำเป็นต้องเรียงข้อมูลก่อน
ขั้นตอนการทำงานของอัลกอริทึม
- เริ่มที่ index 0
- เปรียบเทียบสมาชิกปัจจุบันกับค่าเป้าหมาย
- หากเท่ากันให้คืนค่า index มิฉะนั้นไปยังสมาชิกถัดไป
- คืนค่า -1 เมื่อถึงสมาชิกสุดท้ายแล้วยังไม่พบ
ความซับซ้อน: ใช้เวลา O(n) ในกรณีเฉลี่ยและกรณีแย่ที่สุด และใช้หน่วยความจำเพิ่ม O(1)
ภาพจำลอง การค้นหาเชิงเส้นใน Python
O(n)กด เล่น หรือ ทีละขั้น เพื่อดูการเปรียบเทียบและการย้ายข้อมูลแต่ละขั้น
โค้ดตัวอย่าง
main.py
def linear_search(values, target):
for index, value in enumerate(values):
if value == target:
return index
return -1
print(linear_search([14, 3, 27, 8, 19], 8))ผลลัพธ์ที่คาดหวัง
3หลักการทำงาน
แต่ละค่าถูกเทียบไม่เกินหนึ่งครั้ง ใช้เวลา O(n) และหน่วยความจำ O(1)
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัด
ลองเปลี่ยน input และทดสอบกรณีขอบก่อนใช้ชุดข้อมูลที่ใหญ่ขึ้น
- ทดสอบ input ว่าง หนึ่งสมาชิก และค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นตอน
- เปรียบเทียบประสิทธิภาพกับวิธีอื่น