อัลกอริทึม Python

การค้นหาแบบเชิงเส้น (linear search) ใน Python

ในบทเรียนนี้ คุณจะเขียนการค้นหาแบบเชิงเส้นเพื่อหาตำแหน่งของค่าในลิสต์

  • ระดับกลาง
  • อ่าน 2 นาที
  • ตัวอย่างที่รันได้ 1 ตัวอย่าง

การค้นหาแบบเชิงเส้นคืออะไร?

ปัญหาที่ต้องแก้

บางครั้งข้อมูลไม่ได้เรียง หรือเราค้นหาแค่ครั้งเดียว เช่น รายชื่อสั้น ๆ คำสั่งซื้อของวันนี้ หรือข้อผิดพลาดแรกใน log กรณีแบบนี้เราต้องการวิธีค้นหาที่ง่ายที่สุดและใช้ได้เสมอ

ลองนึกภาพแบบนี้

linear search (การค้นหาแบบเรียงลำดับ) เหมือนการหากุญแจในกระเป๋าเสื้อโค้ตที่แขวนเรียงกันอยู่ เราล้วงกระเป๋าแรก แล้วตัวถัดไป ทีละตัว และหยุดทันทีที่เจอ ถ้าล้วงครบทุกตัวแล้วยังไม่เจอ ก็แปลว่ากุญแจไม่ได้อยู่ในนั้น

จากการตรวจกระเป๋าสู่โค้ด
for index, value in enumerate(values):🧥 ตรวจแต่ละกระเป๋าตามลำดับ
if value == target:🔑 กุญแจอยู่ที่นี่ไหม?
return index✅ เจอแล้ว: หยุดค้นหา
return -1❌ ตรวจครบทุกกระเป๋า: ไม่พบ
ตรวจทีละรายการ หยุดที่ตัวแรกที่ตรง
สรุปในประโยคเดียว

linear search ตรวจสมาชิกในคอลเลกชันทีละตัวจนเจอเป้าหมาย อาจใช้ถึง O(n) ขั้น แต่ไม่ต้องเรียงข้อมูลก่อน

การค้นหาแบบเชิงเส้นตรวจสอบสมาชิกทีละตัวจากต้นรายการจนพบค่าเป้าหมายหรือถึงท้ายรายการ โดยไม่จำเป็นต้องเรียงข้อมูลก่อน

ขั้นตอนการทำงานของอัลกอริทึม

  1. เริ่มที่ index 0
  2. เปรียบเทียบสมาชิกปัจจุบันกับค่าเป้าหมาย
  3. หากเท่ากันให้คืนค่า index มิฉะนั้นไปยังสมาชิกถัดไป
  4. คืนค่า -1 เมื่อถึงสมาชิกสุดท้ายแล้วยังไม่พบ
ความซับซ้อน: ใช้เวลา O(n) ในกรณีเฉลี่ยและกรณีแย่ที่สุด และใช้หน่วยความจำเพิ่ม O(1)

ใช้เมื่อไร?

  • คอลเลกชันที่ไม่ได้เรียงหรือมีขนาดเล็ก
  • ค้นหาครั้งเดียว ซึ่งการเรียงก่อนจะเสียเวลามากกว่า
  • หารายการแรกที่ตรงเงื่อนไข ไม่ใช่แค่ค่าที่ตรงพอดี

เมื่อไรยังไม่จำเป็น

  • ค้นหาหลายครั้งในข้อมูลขนาดใหญ่ชุดเดิม: เรียงครั้งเดียวแล้วใช้ binary search หรือสร้าง set หรือ dictionary
  • ตรวจแค่ว่ามีค่าอยู่ไหม: target in values ทำแบบเดียวกันด้วยโค้ดที่น้อยกว่า

ภาพจำลอง การค้นหาแบบเชิงเส้น (linear search) ใน 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))
สร้างปุ่ม Run สำหรับตัวอย่างนี้

ผลลัพธ์จากการรัน

3

อธิบายโค้ด

ฟังก์ชัน enumerate() ให้ทั้งตำแหน่งและค่าของแต่ละสมาชิก ทันทีที่เจอค่าที่ต้องการ ฟังก์ชันจะคืนตำแหน่งนั้น ในที่นี้คือ 3 ถ้าวนครบทั้งลิสต์แล้วไม่เจอ จะคืน -1 กรณีแย่ที่สุดต้องตรวจทุกสมาชิก ความซับซ้อนจึงเป็น O(n)

เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python

แบบฝึกหัดเพิ่มเติม

ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก

  1. ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
  2. แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
  3. จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
รันในคอมไพเลอร์ Python →

ข้อผิดพลาดที่พบบ่อย

ส่งกลับ -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

เรียนบทนี้จบแล้วใช่ไหม

ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า

ถัดไป: การค้นหาแบบทวิภาค (binary search) ใน Python →

ฝึกด้วยโจทย์

ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI

โจทย์ทั้งหมด