LeetCode #704 Binary Search: บีบช่วงค้นหาโดยไม่หลุดขอบ

โจทย์ binary-search ให้ integer array ที่เรียงจากน้อยไปมากและค่า target ให้คืน index เมื่อพบ หรือ -1 เมื่อไม่มี ความยากไม่ได้อยู่ที่สูตร midpoint แต่อยู่ที่การกำหนดว่าขอบซ้ายและขวารวมอยู่ในช่วงหรือไม่

วิธีที่ 1: linear scan

เดินจากซ้ายจนพบ target เวลา O(n), พื้นที่ O(1) ใช้ได้กับ input เล็กหรือข้อมูลไม่เรียง และเป็น baseline ที่ดี แต่ไม่ใช้ประโยชน์จากเงื่อนไข sorted

วิธีที่ 2: iterative closed interval (แนะนำหลัก)

นิยามช่วง [left, right] ว่ารวมสองขอบ ขณะ left <= right เลือก midpoint ถ้าค่าน้อยไปให้ left = mid + 1 ถ้ามากไปให้ right = mid - 1 ทุก iteration จึงตัด midpoint ออกแน่นอนและจบได้

วิธีที่ 3: recursive binary search

เวลา O(log n) เหมือนกัน แต่ใช้ call stack O(log n) และมี base case เพิ่ม ช่วยสอน divide-and-conquer แต่ใน production iterative version สั้นและไม่มี stack overhead

วิธีที่ 4: bisect_left

standard library หา insertion point ใน O(log n) แล้วตรวจว่าตำแหน่งนั้นเท่ากับ target หรือไม่ เหมาะกับโค้ดจริงเมื่อไม่ต้องแสดงกลไก แต่ในการสัมภาษณ์ควรถามก่อนว่าใช้ library ได้หรือไม่

import bisect
import unittest


def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        middle = left + (right - left) // 2
        if nums[middle] == target:
            return middle
        if nums[middle] < target:
            left = middle + 1
        else:
            right = middle - 1
    return -1


def binary_search_with_bisect(nums, target):
    index = bisect.bisect_left(nums, target)
    return index if index < len(nums) and nums[index] == target else -1


class BinarySearchTests(unittest.TestCase):
    def test_boundaries_and_missing_values(self):
        nums = [-4, -1, 0, 3, 9, 12]
        for target, expected in [(-4, 0), (12, 5), (3, 3), (2, -1)]:
            with self.subTest(target=target):
                self.assertEqual(binary_search(nums, target), expected)
                self.assertEqual(binary_search_with_bisect(nums, target), expected)

    def test_empty_array(self):
        self.assertEqual(binary_search([], 8), -1)


if __name__ == "__main__":
    unittest.main()

Decision table

สถานการณ์	วิธีที่เหมาะ
อาร์เรย์ไม่เรียงหรือสั้นมาก	linear scan
สัมภาษณ์ LeetCode #704	iterative closed interval
สอน recursion	recursive
โค้ด Python production	bisect_left พร้อม equality check

Edge cases ที่ควรทดสอบคืออาร์เรย์ว่าง, สมาชิกเดียว, target ที่ขอบทั้งสอง, target ต่ำ/สูงกว่าทุกค่า และค่าที่หายระหว่างกลาง โจทย์ระบุสมาชิกไม่ซ้ำ หาก requirement เปลี่ยนเป็น “ตำแหน่งแรก” ต้องใช้ lower-bound contract ไม่ควรคืนทันทีที่เจอค่าซ้ำตัวใดก็ได้

Recap

เลือก interval convention หนึ่งแบบ เขียน invariant ก่อน loop และอัปเดตขอบให้ตัด midpoint ทุกครั้ง ค่าเริ่มต้นสำหรับข้อ 704 คือ iterative [left, right]; ในโปรดักชันใช้ bisect_left เมื่อ contract ตรงและตรวจ equality หลังหา insertion point ครับ