บทเรียน: Binary Search
👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ
ค้นหาด้วยการแบ่งครึ่งพื้นที่ค้นหา ลดเหลือ O(log n) — ไม่ได้ใช้แค่กับ array ที่เรียงแล้ว
Binary search หาค่าในข้อมูลที่เรียงแล้วด้วยการแบ่งครึ่งพื้นที่ค้นหาทุกครั้ง จาก O(n) เหลือ O(log n) เช่นข้อมูล 1 ล้านตัวใช้แค่ ~20 ครั้งก็เจอ
Binary search พื้นฐาน
python
def binary_search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
lo = mid + 1 # ไปครึ่งขวา
else:
hi = mid - 1 # ไปครึ่งซ้าย
return -1
print(binary_search([1, 3, 5, 7, 9], 7)) # 3ใช้กับโจทย์ "หาค่าน้อยสุดที่เงื่อนไขเป็นจริง"
binary search ไม่ได้จำกัดแค่หาเลขใน array แต่ใช้กับช่วงคำตอบที่ "เรียงลำดับความเป็นไปได้" ได้ด้วย เช่นหาความเร็วน้อยสุดที่ยังทำงานเสร็จทันเวลา
ข้อควรระวัง
ระวัง off-by-one ตรงการอัปเดต lo/hi และเงื่อนไข while (lo <= hi vs lo < hi) — เขียนผิดนิดเดียวอาจวนไม่จบ ฝึกจนจำ template ได้