搜尋演算法 2 – Binary Search ( 二元搜尋法 )

Binary search 是在已排序好的陣列中最常用的其中一個搜尋演算法。

1. Binary Search 原理解釋

通常如果一個陣列已經排列好的話，就不會再用 linear search 來搜尋目標元素，因為一個一個迭代元素，效率實在太差。Binary Search 的原理是：每次會先和陣列中間的元素比較，因此每次比較會有三個結果：

• 中間元素比目標元素大
• 中間元素比目標元素小
• 中間元素等於目標元素

第三個結果就是找到目標元素，因此就不用繼續再搜尋陣列了。前兩種的話：中間元素比目標元素大：就搜尋左半部的陣列 ( 假設陣列已經由小到大排列 )，中間元素比目標元素小：就搜尋右半部的陣列，並且重複用中間元素來和目標元素比較。

2. JavaScript 實作

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else if (arr[mid] > target) {
      right = mid - 1;
    }
  }
  return -1;
}

3. Time Complexity

最佳的情況就是第一次切割的時候就找到目標元素了，因此時間複雜度是 O(1)。

最差的情況，陣列需要分割 log₂n (因為每次減少一半的搜尋長度)，因此時間複雜度是 O(log n)。

最佳：O(1)
最差：O(log n)
平均：O(log n)

4. 參考資料

資料結構與演算法 (JavaScript)