二分搜尋法教學：原理、程式碼與時間複雜度

二分搜尋法解決什麼問題

線性搜尋逐一檢查每個元素，最多需要 n 次比較。如果資料已經排序，就能做得好得多：把目標與中間的元素比較，立刻就知道該保留哪一半。這和翻紙本字典查字的想法是一樣的。

二分搜尋法也適用於任何具單調性的情況，不限於陣列。如果某個是／否條件在所有小的值上為假、在所有大的值上為真，二分搜尋就能找出分界點。這稱為「對答案做二分搜尋」。

逐步範例

在已排序的串列 [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]（索引 0 到 9）中搜尋 23。我們用兩個索引 lo 與 hi 框住還需要檢查的範圍。

只要三次比較，線性掃描則要六次。對一百萬筆資料的串列，二分搜尋最多只需要 20 次。

Python 實作

下面的迴圈版本使用閉區間 [lo, hi]：兩端都仍是候選位置。只要範圍不是空的，迴圈就繼續執行。

def binary_search(items, target):
    lo, hi = 0, len(items) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            lo = mid + 1          # target is in the right half
        else:
            hi = mid - 1          # target is in the left half
    return -1                     # not found
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(data, 23))   # 5
print(binary_search(data, 7))    # -1

在實際的 Python 程式中，請使用標準函式庫的 bisect 模組。bisect_left 會回傳目標可以插入且維持串列有序的最左邊位置，也能藉此判斷目標是否存在。

from bisect import bisect_left, bisect_right, insort
data = [1, 3, 3, 3, 7, 9]
i = bisect_left(data, 3)
print(i, bisect_right(data, 3))   # 1 4  (3 occupies indexes 1..3)
print(i < len(data) and data[i] == 3)   # True: 3 is present
print(bisect_left(data, 5))       # 4: insertion point for 5
insort(data, 5)
print(data)                       # [1, 3, 3, 3, 5, 7, 9]

時間與空間複雜度

變體：第一個、最後一個，以及對答案做二分搜尋

許多問題問的不是某個值是否存在，而是分界點在哪裡：值至少為 x 的第一個索引、x 最後一次出現的位置，或是滿足條件的最小數字。請使用半開區間 [lo, hi)，而且不要提早停止。

def first_true(lo, hi, ok):
    """Smallest x in [lo, hi) with ok(x) True, or hi if none.
    ok must be False...False True...True over the range."""
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid          # mid may be the answer, keep it
        else:
            lo = mid + 1      # mid is too small
    return lo
data = [1, 3, 3, 3, 7, 9]
print(first_true(0, len(data), lambda i: data[i] >= 3))   # 1
# Integer square root of 200: largest x with x*x <= 200
print(first_true(0, 201, lambda x: x * x > 200) - 1)      # 14

• 下界（值 ≥ x 的第一個索引）：bisect_left。
• 上界（值 > x 的第一個索引）：bisect_right。
• 已排序串列中 x 的個數：bisect_right(a, x) - bisect_left(a, x)。
• 在旋轉過的已排序陣列中搜尋、找峰值，以及最小化最大值（例如在 D 天內運完所有包裹所需的最小載重），都是經典的面試變體題。

常見錯誤

• 混用不同的範圍慣例。閉區間要用 lo <= hi 與 hi = mid - 1；半開區間要用 lo < hi 與 hi = mid。混用會造成無窮迴圈或漏掉元素。
• 寫成 lo = mid 而不是 lo = mid + 1。當 hi = lo + 1 時，mid 等於 lo，迴圈永遠不會結束。
• 對未排序的資料做二分搜尋。它會回傳錯誤的答案，而且不會有任何錯誤訊息。
• 在 Java、C、C++ 這類整數大小固定的語言中，(lo + hi) / 2 可能整數溢位。請改用 lo + (hi - lo) / 2。Python 的整數不會溢位，所以 (lo + hi) // 2 是安全的。
• 題目要求重複值中的第一次出現，卻回傳找到的第一個相符項。

何時使用二分搜尋

實際應用包括資料庫與檔案系統的索引（B 樹是這個想法的推廣）、用 git bisect 找出引入錯誤的提交、在已排序的範圍表（例如 IP 區段）中查值，以及許多需要搜尋門檻值的數值問題。