การค้นหาแบบทวิภาค (binary search) ใน Python
ในบทเรียนนี้ คุณจะเขียนการค้นหาแบบทวิภาคเพื่อหาค่าในลิสต์ที่เรียงแล้วได้อย่างรวดเร็ว
บทนำ
ปัญหาที่ต้องแก้
การหาค่าหนึ่งในลิสต์ล้านรายการด้วยการตรวจทีละรายการอาจใช้การเปรียบเทียบถึงล้านครั้ง เมื่อลิสต์เรียงแล้ว คุณทำได้ดีกว่ามาก: ประมาณ 20 ครั้งก็พอ เพราะการตรวจแต่ละครั้งตัดสิ่งที่เหลือออกไปครึ่งหนึ่ง
ลองนึกภาพแบบนี้
binary search คือวิธีที่คุณเปิดหาคำในพจนานุกรมกระดาษ คุณเปิดตรงกลาง ดูว่าคำของคุณอยู่ก่อนหรือหลังหน้านั้น แล้วทิ้งครึ่งที่ไม่มีทางมีคำนั้น คุณทำซ้ำกับครึ่งที่เหลือจนเจอคำ
low, high = 0, len(values) - 1📖 หน้าที่ยังต้องค้นหาmiddle = (low + high) // 2👆 เปิดตรงกลางlow = middle + 1➡️ คำอยู่ทีหลัง: ทิ้งครึ่งแรกhigh = middle - 1⬅️ คำอยู่ก่อน: ทิ้งครึ่งหลังbinary search หาค่าในลิสต์ที่เรียงแล้วด้วยการเปรียบเทียบกับสมาชิกตรงกลางซ้ำๆ และทิ้งครึ่งที่ไม่มีทางมีค่านั้น ใช้ O(log n) ขั้น
ประเด็นสำคัญ
lowและhighระบุส่วนของลิสต์ที่อาจยังมีเป้าหมายอยู่middle = (low + high) // 2เลือกดัชนีตรงกลางของส่วนนั้น- ถ้า
values[middle] < targetเป้าหมายอยู่ทางขวา จึงตั้งlow = middle + 1มิฉะนั้นตั้งhigh = middle - 1 while low <= high:หยุดเมื่อช่วงว่าง และฟังก์ชันคืน-1ถ้าไม่พบ- สำหรับ 17 การค้นหาตรวจ 12 แล้ว 25 แล้ว 17: เปรียบเทียบสามครั้งแทนสี่ครั้ง
ใช้เมื่อไร?
- ค้นหาในข้อมูลขนาดใหญ่ที่เรียงแล้ว: ID พจนานุกรม log ที่เรียงแล้ว
- หาตำแหน่งที่จะแทรกค่าเพื่อให้ลิสต์ยังเรียงอยู่
- เกมทายตัวเลขและโจทย์ใดก็ตามที่คำตอบถูกบีบให้แคบลงได้ด้วยมากกว่าหรือน้อยกว่า
เมื่อไรยังไม่จำเป็น
- ข้อมูลไม่ได้เรียง: การเรียงเพื่อค้นหาครั้งเดียวแพงกว่า linear search
- ลิสต์เล็กหรือค้นหาครั้งเดียว:
inหรือ dictionary ง่ายกว่า และสำหรับการค้นหาด้วยคีย์หลายครั้ง dict หรือ set ยิ่งเร็วกว่า
ภาพจำลอง การค้นหาแบบทวิภาค (binary search) ใน Python
O(log n)กด เล่น หรือ ทีละขั้น เพื่อดูการเปรียบเทียบและการย้ายข้อมูลแต่ละขั้น
โค้ดตัวอย่าง
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))
ผลลัพธ์จากการรัน
3
อธิบายโค้ด
ตัวแปร low และ high กำหนดช่วงที่ยังต้องค้นหา ถ้าสมาชิกตรงกลางน้อยกว่าค่าที่ต้องการ อัลกอริทึมจะตัดครึ่งซ้ายทิ้งด้วย low = middle + 1 ไม่เช่นนั้นจะตัดครึ่งขวาทิ้ง ความซับซ้อนด้านเวลาคือ O(log n) โดยลิสต์ที่รับเข้ามาต้องเรียงไว้แล้ว
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัดเพิ่มเติม
ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก
- ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
- จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
ข้อผิดพลาดที่พบบ่อย
ใช้ < แทน <= ในลูป
เมื่อใช้ low < high เป้าหมายที่อยู่ในตำแหน่งสุดท้ายที่เหลือจะไม่เคยถูกตรวจ
while low < high:
while low <= high:
ไม่ขยับผ่านตรงกลาง
low = middle อาจได้ตรงกลางเดิมซ้ำไม่รู้จบ
low = middle
low = middle + 1
เรียนบทนี้จบแล้วใช่ไหม
ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า
ฝึกด้วยโจทย์
ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI
- เวลาการผลิตในโรงงาน หาว่าเครื่องจักรหลายเครื่องที่ทำงานพร้อมกันจะสามารถผลิตสินค้าครบตามเป้าหมายได้เร็วที่สุดเมื่อไร ปานกลาง
- ค่ามัธยฐานของสองอาเรย์ที่เรียงลำดับแล้ว หาค่ามัธยฐานของลิสต์ที่เรียงลำดับสองลิสต์เมื่อนำมารวมกัน ยาก