跳至主要内容

Binary Search

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

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

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

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

實作​

// 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;
}

Python 的程式碼，參考自 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

範例​

以 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

解法​

// 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
};
# 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

容易踩的坑​

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

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

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

比較​

把 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 的排序，因此追加數據時可以直接加在最後。
提示

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

最後於 更新