Binary Search

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

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

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

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

白話理解

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

實作

參考自 Ultimate Binary Search Template。

Python

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

JavaScript

function binarySearch(searchSpace) {
  // 內部條件判定函式
  function condition(value) {
    // 依據題目邏輯客製化判定，回傳 true 或 false
    // 當符合條件的情況，直接右邊的資料
  }

  // 設定搜尋空間的起點與終點
  let left = Math.min(...searchSpace);
  let right = Math.max(...searchSpace); 
  // 備註：如果是索引範圍，通常直接設為 0 與 n

  // 雙指標逼近
  while (left < right) {
    let mid = left + Math.floor((right - left) / 2);
    
    if (condition(mid)) {
      // 如果符合條件，代表 mid 可能是答案，但也可能左邊還有更小的答案
      // 所以收縮右邊界，保留 mid 本身 (right = mid)
      right = mid;
    } else {
      // 如果不符合條件，代表答案一定在 mid 的右邊
      // 所以將左邊界排除 mid (left = mid + 1)
      left = mid + 1;
    }
  }
  
  // 當 left === right 時跳出迴圈，此時 left 就是符合條件的最小值（邊界）
  return left;
}

Java

import java.util.Arrays;

class BinarySearch {
    // 內部條件判定介面
    interface Condition {
        boolean test(int value);
    }

    static int binarySearch(int[] searchSpace, Condition condition) {
        // 設定搜尋空間的起點與終點
        int left = Arrays.stream(searchSpace).min().getAsInt();
        int right = Arrays.stream(searchSpace).max().getAsInt();
        // 備註：如果是索引範圍，通常直接設為 0 與 n

        // 雙指標逼近
        while (left < right) {
            int mid = left + (right - left) / 2;

            if (condition.test(mid)) {
                // 如果符合條件，代表 mid 可能是答案，但也可能左邊還有更小的答案
                // 所以收縮右邊界，保留 mid 本身 (right = mid)
                right = mid;
            } else {
                // 如果不符合條件，代表答案一定在 mid 的右邊
                // 所以將左邊界排除 mid (left = mid + 1)
                left = mid + 1;
            }
        }

        // 當 left === right 時跳出迴圈，此時 left 就是符合條件的最小值（邊界）
        return left;
    }
}

範例

以 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

解法

Python

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

JavaScript

var search = function(nums, target) {
    let left = 0
    let right = nums.length - 1

    while (left < right) {
        let mid = left + Math.floor((right - left) / 2)
        if (target <= nums[mid]) { // 條件符合時，去掉 mid 右邊的元素
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    return nums[left] === target ? left : -1
};

Java

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (target <= nums[mid]) { // 條件符合時，去掉 mid 右邊的元素
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return nums[left] == target ? left : -1;
    }
}

逐步拆解

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

輪次	left	right	mid	nums[mid]	判斷	動作
1	0	5	2	3	9 <= 3？否	left = mid + 1 = 3
2	3	5	4	9	9 <= 9？是	right = mid = 4
3	3	4	3	5	9 <= 5？否	left = mid + 1 = 4
結束	4	4	-	-	left === right，跳出迴圈	nums[4] === 9，回傳 4

可以看到每一輪都會直接丟掉一半的搜尋範圍：第一輪丟掉左邊 [-1, 0, 3]，第二輪丟掉右邊的 12，第三輪丟掉 9 左邊剩下的 5，只花 3 輪就鎖定答案，而不需要像 Linear Search 一樣逐一檢查全部 6 個元素。

複雜度

• 時間複雜度：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 的概念很簡單，但卻非常容易寫錯，不少高手也踩坑過，因為邊界值必須要按照不同題目而定。

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

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

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