跳至主要内容

Binary Search

Binary Search 是一種在已經排序好的陣列（SORTED Array） 中搜尋某一特定元素的搜尋演算法。

它的核心思想是「猜數字遊戲」：每次都挑選陣列正中間的元素來與目標值（Target）做比較。

  • 如果中間的值剛好等於目標值，就找到了。
  • 如果中間的值大於目標值，代表目標值一定在左半邊，此時可以直接把右半邊全部丟掉。
  • 如果中間的值小於目標值，代表目標值一定在右半邊，可以直接把左半邊全部丟掉。

因為每次都去掉一半的資料，因此 Time complexity 為 O(log n)。

白話理解

就像玩猜數字遊戲：主持人只會告訴你「太大」或「太小」，聰明的猜法不是從 1 開始一個一個猜，而是先猜正中間的數字，再依據「太大」或「太小」直接刪掉一半的可能範圍，一輪一輪把範圍砍半，很快就能鎖定答案。

模板​

參考自 Ultimate Binary Search Template。

def binary_search(array) -> int:
    def condition(value) -> bool: # 根據題目內容客製條件
        pass

    left, right = min(search_space), max(search_space) 
    ## 通常是 [0, n], [1, n]，根據題目而定
    
    while left < right:
        mid = left + (right - left) // 2 # 一般情況可寫 (left + right) // 2
        if condition(mid):
            right = mid
        else:
            left = mid + 1
    return left
C++/Java 的整數範圍要留意

Python 的整數沒有固定寬度，不會溢位。但 C++、Java 的 int 通常是 32 位元（約 ±21 億）。上面的範本用 int 示範 searchSpace、left、right，如果拿這個範本去解「二分搜尋答案空間」類型的題目，而答案的數值範圍可能超過 2^31 - 1（例如貨物總重量、座標總和這類可能很大的數字），記得把 C++、Java 裡的 left、right、mid 改成 long long／long，避免計算過程中溢位。

另一種寫法：雙閉區間 + 顯式記錄答案​

上面這個「Ultimate Binary Search Template」用的是 while left < right、right = mid 的單邊收斂寫法，數學上很漂亮：left 跟 right 收斂到同一個點，那個點就是答案，不需要額外變數。

但這個寫法有一個明顯缺點，寫的時候要先把題目的 「符合 / 不符合」在腦中轉換成「找一個分界點」，如果更新邊界時寫反一個地方（例如把 left = mid + 1 誤寫成 left = mid），就會卡進無窮迴圈。

另一種常見寫法是 while left <= right，搭配一個額外變數顯式記錄「目前為止最好的答案」：

def binary_search(array) -> int:
    def condition(value) -> bool: # 根據題目內容客製條件
        pass

    left, right = min(search_space), max(search_space)
    ans = -1  # 預設值依題目而定，-1 代表「還沒找到」

    while left <= right:
        mid = left + (right - left) // 2
        if condition(mid):
            ans = mid         # 符合條件，先記下來
            right = mid - 1   # 找最小符合條件的值，繼續往左找
            # left = mid + 1  # 若要找最大符合條件的值，改成繼續往右找
        else:
            left = mid + 1
            # right = mid - 1 # 對應上面找最大值時，這裡也要對調方向
    return ans

兩種寫法比較一下：

比較項目while left <= right（雙閉區間）while left < right（單邊收斂）
無窮迴圈風險幾乎沒有，left、right 每次都嚴格 ±1有風險，right = mid 若搭配錯誤的 left 更新方式容易卡住
思考難度低，condition(mid) 可以照題目直覺寫較高，要先轉換成「找分界點」的框架才能套用
回傳值直接回傳 ans，不用煩惱最後該回傳 left 還是 right迴圈結束時 left === right，但要能推導出這就是答案
適用場景所有情境都適用，尤其是面試這種高壓場合程式碼稍微精簡，熟悉之後寫起來比較快
我現在的選擇

這兩種寫法能解決的問題是一樣的，差別只在「怎麼收斂」。

我目前更推薦 while left <= right 這個版本：它用一個額外的 ans 變數把「記錄答案」跟「維護搜尋範圍」兩件事分開，left、right 只負責單純地逼近，不需要同時兼顧「收斂後自己就是答案」這件事。

這在面試這種需要一邊講解、一邊在壓力下寫程式碼的場合特別重要——少一個需要同步想清楚的細節，就少一個出錯的機會。下面的解法範例會直接示範這個寫法。

範例​

以 LeetCode 題目 Binary Search 當範例

題目：給定一個升序排序的整數陣列 nums 與目標值 target，需實作一個時間複雜度為 O(log n) 的演算法來搜尋目標，若存在則返回索引，否則返回 -1。

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

解法​

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        ans = -1
        while left <= right:
            mid = left + (right - left) // 2
            if target <= nums[mid]:
                ans = mid
                right = mid - 1
            else:
                left = mid + 1
        return ans if ans != -1 and nums[ans] == target else -1

逐步拆解​

以 nums = [-1, 0, 3, 5, 9, 12]、target = 9 為例：

輪次leftrightmidnums[mid]判斷動作ans
105239 <= 3？否left = mid + 1 = 3-1
235499 <= 9？是ans = 4；right = mid - 1 = 34
333359 <= 5？否left = mid + 1 = 44
結束43--left > right，跳出迴圈回傳 ans：nums[4] === 9，回傳 44

可以看到每一輪都會直接丟掉一半的搜尋範圍：第一輪丟掉左邊 [-1, 0, 3]，第二輪丟掉右邊的 12，第三輪丟掉 9 左邊剩下的 5，只花 3 輪就鎖定答案，而不需要像 Linear Search 一樣逐一檢查全部 6 個元素。整個過程中答案一直存在 ans 裡，迴圈結束直接回傳 ans 即可，不用再去想「最後該回傳 left 還是 right」。

複雜度​

  • 時間複雜度：O(log n)，因為每一輪都會丟掉一半的搜尋範圍。
  • 空間複雜度：O(1)，只需要 left、right、mid 幾個變數，不需要額外的資料結構。
提示

務必要記得，Binary Search 適用於 SORTED Array，如果 array 是雜亂無序的，則必須先排序好。
排序的時間複雜度是 O(n log n)，如果得先排序再用 Binary Search，那不如用 Linear Search O(n)。

比較​

把 Binary Search 和 Linear Search 一起比較。
（Linear Search 就是大家比較熟悉的方法，直接檢查每一個元素）

  • Binary Search

    • Time complexity 為 O(log n)，但只對 sorted array 有用。
    • 所以要一直讓這個方法有效的話，則在追加數據時要插入適當的位置，也就是得付出維護 array 的代價。

  • Linear Search

    • Time complexity 為 O(n)，但 array 有沒 sorted 都可用。
    • Linear Search 雖然慢得多，但是不限制 array 的排序，因此追加數據時可以直接加在最後。

適用情況​

  • 已排序資料中的精確搜尋：例如在排序好的使用者 ID 清單中，快速找出特定 ID 是否存在。
  • 尋找邊界 / 插入位置：例如 Leetcode: Search Insert Position，找出目標值該插入的位置，或找出符合條件的第一 / 最後一個元素。
  • 在答案空間上做二分搜尋（Binary Search on Answer）：題目本身不是搜尋陣列，而是搜尋「答案的可能範圍」，只要能寫出單調的 condition 判斷式（符合條件、不符合條件呈現一刀切的分界），就能套用 Binary Search Template 找出邊界值。

常見誤區​

Binary Search 的概念很簡單，但卻非常容易寫錯，不少高手也踩坑過，因為邊界值必須要按照不同題目而定。

  • 邊界更新寫錯：用單邊收斂寫法（while left < right）時，right = mid 還是 right = mid - 1、left = mid + 1 還是 left = mid，必須依照「mid 有沒有可能還是答案」來決定，寫錯容易造成無窮迴圈或漏掉正確答案；這也是前面建議改用雙閉區間寫法（while left <= right + ans）的原因之一，left、right 固定用 mid ± 1 更新，不會有這個問題。
  • 陣列沒有排序就直接套用：Binary Search 的正確性建立在「排序好」這個前提上，對未排序陣列使用會得到錯誤結果。
  • 誤以為只能用在陣列上：只要能定義出一個具有單調性（符合 / 不符合條件會一刀切）的判斷式，就能套用 Binary Search 的框架，不限於在實際陣列上搜尋。

我推薦觀看這個影片，可更加深入了解並避坑：

如果你習慣看中文講解，也可以參考下方這個影片，但是和上面的寫法不一樣，請自行參考：

最後於 更新