การค้นหาแบบเชิงเส้น (linear search) ใน Python
ในบทเรียนนี้ คุณจะเขียนการค้นหาแบบเชิงเส้นเพื่อหาตำแหน่งของค่าในลิสต์
การค้นหาแบบเชิงเส้นคืออะไร?
ปัญหาที่ต้องแก้
บางครั้งข้อมูลไม่ได้เรียง หรือเราค้นหาแค่ครั้งเดียว เช่น รายชื่อสั้น ๆ คำสั่งซื้อของวันนี้ หรือข้อผิดพลาดแรกใน log กรณีแบบนี้เราต้องการวิธีค้นหาที่ง่ายที่สุดและใช้ได้เสมอ
ลองนึกภาพแบบนี้
linear search (การค้นหาแบบเรียงลำดับ) เหมือนการหากุญแจในกระเป๋าเสื้อโค้ตที่แขวนเรียงกันอยู่ เราล้วงกระเป๋าแรก แล้วตัวถัดไป ทีละตัว และหยุดทันทีที่เจอ ถ้าล้วงครบทุกตัวแล้วยังไม่เจอ ก็แปลว่ากุญแจไม่ได้อยู่ในนั้น
for index, value in enumerate(values):🧥 ตรวจแต่ละกระเป๋าตามลำดับif value == target:🔑 กุญแจอยู่ที่นี่ไหม?return index✅ เจอแล้ว: หยุดค้นหาreturn -1❌ ตรวจครบทุกกระเป๋า: ไม่พบlinear search ตรวจสมาชิกในคอลเลกชันทีละตัวจนเจอเป้าหมาย อาจใช้ถึง O(n) ขั้น แต่ไม่ต้องเรียงข้อมูลก่อน
การค้นหาแบบเชิงเส้นตรวจสอบสมาชิกทีละตัวจากต้นรายการจนพบค่าเป้าหมายหรือถึงท้ายรายการ โดยไม่จำเป็นต้องเรียงข้อมูลก่อน
ขั้นตอนการทำงานของอัลกอริทึม
- เริ่มที่ index 0
- เปรียบเทียบสมาชิกปัจจุบันกับค่าเป้าหมาย
- หากเท่ากันให้คืนค่า index มิฉะนั้นไปยังสมาชิกถัดไป
- คืนค่า -1 เมื่อถึงสมาชิกสุดท้ายแล้วยังไม่พบ
ใช้เมื่อไร?
- คอลเลกชันที่ไม่ได้เรียงหรือมีขนาดเล็ก
- ค้นหาครั้งเดียว ซึ่งการเรียงก่อนจะเสียเวลามากกว่า
- หารายการแรกที่ตรงเงื่อนไข ไม่ใช่แค่ค่าที่ตรงพอดี
เมื่อไรยังไม่จำเป็น
- ค้นหาหลายครั้งในข้อมูลขนาดใหญ่ชุดเดิม: เรียงครั้งเดียวแล้วใช้ binary search หรือสร้าง set หรือ dictionary
- ตรวจแค่ว่ามีค่าอยู่ไหม:
target in valuesทำแบบเดียวกันด้วยโค้ดที่น้อยกว่า
ภาพจำลอง การค้นหาแบบเชิงเส้น (linear search) ใน Python
O(n)กด เล่น หรือ ทีละขั้น เพื่อดูการเปรียบเทียบและการย้ายข้อมูลแต่ละขั้น
โค้ดตัวอย่าง
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
อธิบายโค้ด
ฟังก์ชัน enumerate() ให้ทั้งตำแหน่งและค่าของแต่ละสมาชิก ทันทีที่เจอค่าที่ต้องการ ฟังก์ชันจะคืนตำแหน่งนั้น ในที่นี้คือ 3 ถ้าวนครบทั้งลิสต์แล้วไม่เจอ จะคืน -1 กรณีแย่ที่สุดต้องตรวจทุกสมาชิก ความซับซ้อนจึงเป็น O(n)
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัดเพิ่มเติม
ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก
- ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
- จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
ข้อผิดพลาดที่พบบ่อย
ส่งกลับ -1 ข้างในลูป
การค้นหาจะเลิกทันทีหลังเจอรายการแรกที่ไม่ตรง
for index, value in enumerate(values):
if value == target:
return index
return -1
for index, value in enumerate(values):
if value == target:
return index
return -1
เรียนบทนี้จบแล้วใช่ไหม
ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า
ฝึกด้วยโจทย์
ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI
- First Negative Index Find where the first negative number appears. ง่าย
- หาค่าน้อยสุดในอาเรย์ หาค่าที่น้อยที่สุดในลิสต์ ง่าย