Binary search 是一種在有序陣列做搜尋的演算法，在最壞的狀況下，其時間複雜度為 O (log n) 對數時間，相當高效。

Binary search 框架

以下是 binary search 的框架，但只適用於有序且不含重複元素的 Array ：

int bsearch(vector<int>& a, int value) {
    int low = 0;
    int high = a.size()-1;

    while (low <= high) {
        int mid = low + ((high-low)>>1);
        if (a[mid] == value) {
            return mid;
        } else if (a[mid] < value) {
            low = mid + 1;
        } else if (a[mid] > value) {
            high = mid - 1;
        }
    }
    return -1;
}

3個實作上容易犯的錯誤：

1. while loop 終止條件
   注意是 low ≤ high ，不是 low < high 。
   由於 high 的初始值為 a.size()-1 ，是陣列的最後一個 index ，代表我們的搜尋區間是 [left, right] (左右兩邊的邊界元素都是可以被搜尋的，將這樣狀況稱為左閉右閉)，當區間內找到目標值，就可以直接回傳，如果區間內所有元素都找完了，while 迴圈也會終止，就可以直接回傳 -1 。

   另外一個退出條件的理解方式，當 while (low <= high) 終止時，代表此時 left == right+1 ，代表當前的搜尋區間為 [right+1, right] ，帶個具體數字為 [3, 2] ，可見這個時候搜尋區間為空集合。

2. low 和 high 的更新

   沒寫好會進入無窮迴圈。
   只要將搜尋區間的概念理解清楚，就不會被是否要 +1 還是 -1 困惑。由於搜尋區間為 [left, right] ，當 mid 對應的數字搜尋過後，接著要搜尋的區間就會是 [left, mid-1] 或是 [mid+1, right] ，一開始採取左閉右閉的搜尋方式，在處理完 mid 後當然還是以左閉右閉的方式繼續 。

3. mid 的取值
   mid = ( low + high ) / 2 可能會發生 overflow ；如果追求性能的話，還可以將除以 2 改寫為 >> 1 ，取中間值可寫為 low + ( (high - low) >> 1) 。

使用限制

這個框架使用上有限制：

1. 只能用於 array 上。
2. 尋找的數據本身必須有依照順序排列。如果是插入或刪除操作相當頻繁的話，必須確保執行完操作後，資料間依然是有序的。
3. 資料量不夠大的話，直接依序搜尋就可。
4. binary search 依賴 array 這個資料結構，但如果資料數量太大，代表會消耗很大一塊的連續記憶體，因此在 input 資料過大狀況下，又要使用 array （以方便作 binary search ）的話是不太明智的。

Binary search 變形題

透過 binary search 去找目標值其實不怎麼常用，碰到找目標值的問題更傾向用 hash table 或是 binary tree，反倒是以下所列的變形題難以透過 hash table 或是 binary tree 來實現，就適合以 array 搭配 binary search 來解題，這類變形題如下：

1. 找第一個值等於目標值的元素
2. 找最後一個值等於目標值的元素
3. 找第一個大於等於目標值的元素
4. 找最後一個小於等於目標值的元素

接著來探討一個變形題並說明為何上面的框架不適用。

Leetcode #35 Search Insert Position

在陣列中找出比目標值還小的數有幾個？

int bsearch(vector<int>& a, int value) {
  int low = 0;
  int high = a.size();  // (1)

  while (low < high) {  // (2)
    int mid = low + ((high-low)>>1);
    if (a[mid] == value) {
      high = mid;   // (4)
    } else if (a[mid] < value) {
        low = mid + 1;  // (3)
    } else if (a[mid] > value) {
        high = mid; // (3)
    }
  }
  return low;       // (5)
}

我註解了 5 個地方，這 5 個地方與前面提供的框架有所不同，下面來解釋他們的差異。

(1) 為什麼 high 的初值設定為 a.size() ?

見下圖，這題可能的答案為 0 ~ a.size() 。

若將 high 的初值設為 a.size() - 1 ，在迴圈終止後還需要特別處理答案為 a.size() 的 edge case ，因此選擇將 high 設定為a.size() 對程式碼的撰寫更合適。但需注意，搜尋區間將變為 [low, high) ，等同於左閉右開。

(2) 為什麼 while 迴圈終止條件是 low < high ?! 而不是 low ≤ high ？

不應該拘泥於到底該不該有等號，應該掌握的是搜尋區間並依照題目需求做調整。

while (low < high) 的終止條件為 low == high ，寫成區間形式為 [low, low) ，這時候區間被收斂到剩下一個元素，剩下一個元素你還繼續作 binary search 的話，那就永遠困在迴圈裡了(證明可見此連結），如果證明懶得看的話，可以用只有兩個元素的 case 來自我測試，你就會了解為什麼不能夠有等號。

while 迴圈的終止條件判斷式是整個 binary search 過程的 loop invariant (迴圈不變式) ，不論迴圈怎麼迭代， loop invariant 都必須為 true ，這個概念貫穿整個 binary search 的過程。

(3) 為什麼 low 跟 high 的更新跟之前不一樣？

如同前面提到的，要將搜尋區間掌握清楚，由於答案可能為 0~ a.size() ，但是 a.size() 不可能作為搜尋區間內的元素，因此採用了左閉右開的區間 [low, high) ，當 a[mid] 被檢查後，搜尋區間被切為兩塊，分別是 [low, mid) 和 [mid+1, high) ，所以 low 跟 high 的更新自然跟著你的搜尋區間來變化。

(4) 為什麼這個框架可以用來找到比目標值還小的數有幾個？

關鍵在於當 a[mid] == target 時，不要回傳，而是執行 high = mid ，如果 mid 位置上為 target ，代表 mid 本身和其右邊的元素都不再需要被關注，透過將搜索區間右邊縮小，不斷的收斂就能找到比目標值小的數量。

(5) 回傳的是 low ，為什麼不是 high ？

當 while 終止時，其終止條件為 low == high ，因此回傳 low 或是 high 是沒有差別的。

但為什麼這個框架更適合解決變形題？

其實以本文開頭的框架來解題也是可以，但是有機會 low 所指向的是一個空的元素。第一個框架的終止條件為 low = high+1 ，若是 high 為右邊邊界的 index a.size()-1，則 low 就會變成不在區間內的空元素 a,size()，若是 low 為左邊邊界的 index 0 ，則 high 會變為 -1 ，因此以第一個框架來說，你就會需要多思考遇到這樣的 case ，到底該回傳的是 low, mid 還是 high 。

但是以第二個框架，low 永遠都會指向一個在搜尋區間內確實存在的元素，這兩個方法並沒有對錯，就看自己比較可以理解哪一種。

結論

這麼多不同的細節，相信不可能用死背的，重點是你要理解搜尋區間的概念，清楚知道你正在操作的區間範圍，接下來將有相關文章探討更多 binary search 的變形題及其對應的框架。

• Binary Search (2) Template Overview
• Binary Search (3) template III 應用
• Binary Search (4) 進階問題

Reference

1. Binary Search - Leetcode Explore
2. [Python] Powerful Ultimate Binary Search Template. Solved many problems - Leetcode
3. 我作了首诗，保你闭着眼睛也能写对二分查找 - labuladong
4. 二分搜索只能用来查找元素吗？ - labuladong
5. 数组：每次遇到二分法，都是一看就会，一写就废

Updated on 2022-12-31 16:54:49 星期六