Binary search — 二分搜尋法

發表於 更新於 分類於
利用將資料切一半的方式來做搜尋，舉例來說，如果要從數字1–100猜終極密碼，如果採用線性搜尋法就是一個一個問?是1嗎?是2嗎?…依序猜下去，很不幸的數字剛好是99就需要猜99次，但如果用二分搜尋法就會是先判斷數字是否大於50 ，如果是的話那是否大於75…

利用將資料切一半的方式來做搜尋，舉例來說，如果要從數字 1–100 猜終極密碼，如果採用線性搜尋法就是一個一個問?是 1 嗎?是 2 嗎?…依序猜下去，很不幸的數字剛好是 99 就需要猜 99 次，但如果用二分搜尋法就會是先判斷數字是否大於 50 ，如果是的話那是否大於 75 ，依此類推每次都用對半砍的方式縮小範圍，最後只需要猜七次就能猜出終極密碼。

使用二分搜尋法的前提必須是先排序過

假設目前有個陣列:[10, 21, 34, 50, 66,79, 82, 97]，要找出陣列中是否有 79 這個數字，有的話就回傳 79 在哪個 index

這邊運用到雙指針的概念來解題(left, right)，關於雙指針的說明可以參考這篇文章， 這裡可以先想像有兩個指針會不斷往中間靠攏，進而縮短搜尋區間。

實作的概念為:

  1. 先在陣列取一個中間數的 index，公式為 Math.floor((left+right)/2)，0+7 除以 2 無條件捨去後拿到 3，這邊用 middle 標示為中間數。

2. 這時拿目標數 79 去跟中間數 50 比較，目標數 79 比較大，代表中間數的左邊那堆數字都不可能是我們要找的答案(都太小了)，所以我們要調整一下搜尋範圍，將 left 指針移動到 middle+1 的位置。

為甚麼要 middle+1?因為已經知道 middle 不是答案，搜尋範圍就可以排除 middle 了

3.重新計算中間數，(4+7)/2 無條件捨去算出 5，而在 index 5 的數字 79 就是我們要找的數字。

用 js 實作二分搜尋法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const binarySearch = (arr, num) => {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    let middle = Math.floor((left + right) / 2);
    if (num === arr[middle]) return middle;
    if (num > arr[middle]) {
      left = middle + 1;
    } else if (num < arr[middle]) {
      right = middle - 1;
    }
  }
  return -1;
};

binarySearch([10, 21, 34, 50, 66, 79, 82, 97], 79);

時間複雜度

👍 在最差的情況下，時間複雜度是 O(log n)

👎 在最佳的情況下，時間複雜度是 O(1)

🤚 在平均情況下，時間複雜度為 O(log n)