อัลกอริทึม Python

การค้นหาแบบทวิภาค (binary search) ใน Python

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

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

บทนำ

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

การหาค่าหนึ่งในลิสต์ล้านรายการด้วยการตรวจทีละรายการอาจใช้การเปรียบเทียบถึงล้านครั้ง เมื่อลิสต์เรียงแล้ว คุณทำได้ดีกว่ามาก: ประมาณ 20 ครั้งก็พอ เพราะการตรวจแต่ละครั้งตัดสิ่งที่เหลือออกไปครึ่งหนึ่ง

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

binary search คือวิธีที่คุณเปิดหาคำในพจนานุกรมกระดาษ คุณเปิดตรงกลาง ดูว่าคำของคุณอยู่ก่อนหรือหลังหน้านั้น แล้วทิ้งครึ่งที่ไม่มีทางมีคำนั้น คุณทำซ้ำกับครึ่งที่เหลือจนเจอคำ

จากพจนานุกรมกระดาษสู่โค้ด
low, high = 0, len(values) - 1📖 หน้าที่ยังต้องค้นหา
middle = (low + high) // 2👆 เปิดตรงกลาง
low = middle + 1➡️ คำอยู่ทีหลัง: ทิ้งครึ่งแรก
high = middle - 1⬅️ คำอยู่ก่อน: ทิ้งครึ่งหลัง
ทุกการเปรียบเทียบลดสิ่งที่เหลือลงครึ่งหนึ่ง ลิสต์ขนาดใหญ่มากจึงใช้ไม่กี่ขั้น
สรุปในประโยคเดียว

binary search หาค่าในลิสต์ที่เรียงแล้วด้วยการเปรียบเทียบกับสมาชิกตรงกลางซ้ำๆ และทิ้งครึ่งที่ไม่มีทางมีค่านั้น ใช้ O(log n) ขั้น

ประเด็นสำคัญ

  1. low และ high ระบุส่วนของลิสต์ที่อาจยังมีเป้าหมายอยู่
  2. middle = (low + high) // 2 เลือกดัชนีตรงกลางของส่วนนั้น
  3. ถ้า values[middle] < target เป้าหมายอยู่ทางขวา จึงตั้ง low = middle + 1 มิฉะนั้นตั้ง high = middle - 1
  4. while low <= high: หยุดเมื่อช่วงว่าง และฟังก์ชันคืน -1 ถ้าไม่พบ
  5. สำหรับ 17 การค้นหาตรวจ 12 แล้ว 25 แล้ว 17: เปรียบเทียบสามครั้งแทนสี่ครั้ง

ใช้เมื่อไร?

  • ค้นหาในข้อมูลขนาดใหญ่ที่เรียงแล้ว: ID พจนานุกรม log ที่เรียงแล้ว
  • หาตำแหน่งที่จะแทรกค่าเพื่อให้ลิสต์ยังเรียงอยู่
  • เกมทายตัวเลขและโจทย์ใดก็ตามที่คำตอบถูกบีบให้แคบลงได้ด้วยมากกว่าหรือน้อยกว่า

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

  • ข้อมูลไม่ได้เรียง: การเรียงเพื่อค้นหาครั้งเดียวแพงกว่า linear search
  • ลิสต์เล็กหรือค้นหาครั้งเดียว: in หรือ dictionary ง่ายกว่า และสำหรับการค้นหาด้วยคีย์หลายครั้ง dict หรือ set ยิ่งเร็วกว่า

ภาพจำลอง การค้นหาแบบทวิภาค (binary search) ใน Python

O(log n)

กด เล่น หรือ ทีละขั้น เพื่อดูการเปรียบเทียบและการย้ายข้อมูลแต่ละขั้น

โค้ดตัวอย่าง

รันโค้ด →
main.py
def binary_search(values, target):
    low, high = 0, len(values) - 1
    while low <= high:
        middle = (low + high) // 2
        if values[middle] == target:
            return middle
        if values[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return -1

print(binary_search([3, 8, 12, 17, 25, 31], 17))
สร้างปุ่ม Run สำหรับตัวอย่างนี้

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

3

อธิบายโค้ด

ตัวแปร low และ high กำหนดช่วงที่ยังต้องค้นหา ถ้าสมาชิกตรงกลางน้อยกว่าค่าที่ต้องการ อัลกอริทึมจะตัดครึ่งซ้ายทิ้งด้วย low = middle + 1 ไม่เช่นนั้นจะตัดครึ่งขวาทิ้ง ความซับซ้อนด้านเวลาคือ O(log n) โดยลิสต์ที่รับเข้ามาต้องเรียงไว้แล้ว

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

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

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

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

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

ใช้ < แทน <= ในลูป

เมื่อใช้ low < high เป้าหมายที่อยู่ในตำแหน่งสุดท้ายที่เหลือจะไม่เคยถูกตรวจ

ปัญหา
while low < high:
วิธีแก้
while low <= high:

ไม่ขยับผ่านตรงกลาง

low = middle อาจได้ตรงกลางเดิมซ้ำไม่รู้จบ

ปัญหา
low = middle
วิธีแก้
low = middle + 1

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

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

ถัดไป: การเรียงแบบฟอง (bubble sort) ใน Python →

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

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

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