Binary Search — พื้นฐาน & แนวคิด

Binary Search (ค้นหาแบบแบ่งครึ่ง) คือหนึ่งในเทคนิคที่คุ้มค่าที่สุดที่ควรมีติดตัว ไอเดียเรียบง่ายมาก: ถ้าของ sorted (เรียงลำดับ) อยู่แล้ว ทุกครั้งที่ guess (เดา) เราสามารถ eliminate (ตัดทิ้ง) ตัวเลือกไปครึ่งหนึ่งได้ทันที ทำให้ search (ค้นหา) ของใน array (ลิสต์) ล้านตัวได้ในราว 20 ก้าวเท่านั้น หน้านี้จะปูตั้งแต่ binary search แบบพื้นฐาน ไปจนถึงเทคนิคขั้นสูงที่เรียกว่า binary search on answer

แนวคิดพื้นฐาน & template lo/hi/mid

ลองนึกถึงการเปิด dictionary (พจนานุกรม) หาคำ เราไม่ได้เปิดทีละหน้าจากหน้าแรก แต่เปิดกลางเล่มก่อน ถ้าคำที่หาอยู่ก่อนหน้านั้นก็ตัดครึ่งหลังทิ้ง ถ้าอยู่หลังก็ตัดครึ่งแรกทิ้ง แล้วทำซ้ำกับครึ่งที่เหลือ นี่คือ binary search เป๊ะ ๆ เงื่อนไขสำคัญคือ ของต้อง sorted แล้ว เท่านั้นเราถึงจะรู้ว่าควร eliminate ครึ่งไหน

ทำไมมันเร็ว? เพราะทุกก้าวเรา halve (ลดครึ่ง) ขนาดปัญหา array n ตัว จะแบ่งครึ่งได้ราว log2(n) ครั้งก่อนเหลือตัวเดียว เช่น n = 1,000,000 ใช้แค่ประมาณ 20 ก้าว เทียบกับการ iterate (ไล่วน) ทีละตัว O(n) ที่ต้องดูถึงล้านครั้ง นี่คือความต่างระหว่าง O(log n) กับ O(n)

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             # target อยู่ครึ่งขวา ตัดครึ่งซ้ายทิ้ง
        else:
            hi = mid - 1             # target อยู่ครึ่งซ้าย ตัดครึ่งขวาทิ้ง
    return -1                        # ไม่เจอ

print(binary_search([1, 3, 5, 7, 9, 11], 7))  # 3
print(binary_search([1, 3, 5, 7, 9, 11], 4))  # -1

เทคนิคขั้นสูง: Binary Search on Answer

นี่คือแนวคิดที่ทำให้ binary search ทรงพลังกว่าที่คิดมาก แทนที่จะ search ค่า ใน array ที่ sorted ไว้ เรากลับ search คำตอบ ใน answer space (ช่วงของคำตอบที่เป็นไปได้ทั้งหมด) หลักการคือ ถ้าเรา guess คำตอบเป็นตัวเลข x แล้วมี function (ฟังก์ชัน) check ได้ว่า x นี้ feasible (ใช้ได้) ไหม และคำตอบมีลักษณะ monotonic (ยิ่งมากยิ่งง่าย หรือยิ่งน้อยยิ่งง่าย) แบบขั้นบันได เราก็ binary search หา boundary (จุดพลิก) ได้เลย

ตัวอย่างที่ชัดคือ LC875 (Koko Eating Bananas / โกโกะกินกล้วย) ที่จะเจอเป็นข้อสุดท้าย speed (ความเร็ว) กินยิ่งมาก ยิ่งกินทันแน่ ๆ speed ยิ่งน้อยยิ่งเสี่ยงไม่ทัน เงื่อนไข กินทันไหม จึงเป็นขั้นบันได true-false ที่เรียงตัว เราจึง binary search บนช่วง speed 1 ถึง max เพื่อหา speed น้อยสุดที่ยัง feasible

# template ของ binary search on answer (หาค่าน้อยสุดที่ feasible)
def search_on_answer(lo, hi, feasible):
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid          # mid ใช้ได้ ลองหาค่าที่น้อยกว่านี้ต่อ (เก็บ mid ไว้)
        else:
            lo = mid + 1      # mid ใช้ไม่ได้ ต้องมากขึ้น
    return lo                 # จุดพลิกจาก ใช้ไม่ได้ -> ใช้ได้