Binary Search

搜尋演算法 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)。

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

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

4. 參考資料

資料結構與演算法 (JavaScript)

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top