การค้นหาแบบทวิภาคใน Python
Binary search ลดขอบเขตค้นหาลงครึ่งหนึ่งทุกครั้งที่เปรียบเทียบ
การค้นหาแบบทวิภาคใน Python คืออะไร?
Binary search ลดขอบเขตค้นหาลงครึ่งหนึ่งทุกครั้งที่เปรียบเทียบ
ค้นหาค่าอย่างรวดเร็วใน list ที่เรียงแล้ว
ควรใช้เมื่อใด?
- ทำความเข้าใจอัลกอริทึมและโครงสร้างข้อมูล
- สังเกตแต่ละขั้นตอนและกรณีขอบ
- เปรียบเทียบเวลาและหน่วยความจำ
ภาพจำลอง การค้นหาแบบทวิภาคใน 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))ผลลัพธ์ที่คาดหวัง
3หลักการทำงาน
ค่ากลางกำหนดว่าจะเก็บครึ่งซ้ายหรือขวา ใช้เวลา O(log n) และ input ต้องเรียงแล้ว
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัด
ลองเปลี่ยน input และทดสอบกรณีขอบก่อนใช้ชุดข้อมูลที่ใหญ่ขึ้น
- ทดสอบ input ว่าง หนึ่งสมาชิก และค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นตอน
- เปรียบเทียบประสิทธิภาพกับวิธีอื่น