二分搜尋法 Binary Search

如何在一堆東西裡面尋找我想要的東西呢?相向大家都有相似的疑問吧?
這章節會介紹兩個常用的搜尋演算法

線性搜尋法 Linear Search

找東西最直觀的方法就是把所有東西掃過一遍，這樣就可以找到想要的內容了
而這種方法就叫做線性搜尋法
線性搜尋法很簡單，對於一個陣列，只需要一個一個比較是否相同即可

int arr[7] = {1, 4, 8, 13, 42, 89, 101};
int target = 42; // 目標值
for(int i = 0; i < 7; i++){
    if(arr[i] == target) // 判斷 arr[i] 是否為 target
        cout << "Found!!\n"; 
}

時間複雜度:

$O(n)$
但是這樣就太慢了!!

二分搜尋法 Binary Search

介紹

二分搜尋法的精神就是把一個序列剖半、比較、再剖半、再比較…直到找到答案為止

在以下影片中，目標是尋找一區間中的紅線，黑線代表中線
那們會執行以下流程:

1. 藉由左右界找到中線位置
2. 發現紅線是在中線的右半邊
3. 捨棄左半邊不看(將新左界設在中線的位置)
4. 找出新的中線位置
5. 發現紅線在中線的左半邊
6. 捨棄右半邊不看(將新右界設在中線的位置)
7. 找出新的中線位置
8. 發現紅線剛好在中線上(結束!!)

---

舉例

假設有一陣列

$arr[7]=\{1,4,8,13,42,89,101\}$，目標是希望找到

$42$
在這其中，我們可以使用三個指針

$L,M,R$ 來維護

---

實作

二分搜尋法需要先準備好一個「有序」的序列與一個目標值
最後會回傳目標值在序列中的位置

int arr[7] = {1, 4, 8, 13, 42, 89, 101};
int target = 42, n = 7; 
int l = 0, r = n - 1;  // 搜尋 [l, r] 區間
while (l <= r) {
    int m = (l + r) / 2;
    if (arr[m] == target){
        cout << "Found target";
        break;
    }
    else if (arr[m] < target)
        l = m + 1;
    else  (arr[m] > target)
        r = m - 1;
}

詳細流程如下:

PS : 實作時如果遇到無限迴圈，可以檢查是否維護好邊界或是終止條件

單調性

二分搜尋法基本上符合單調性的任何東西都可以使用
單調性基本上就是對於一個函數

$f(x)$:
當

$x$ 越大

$f(x)$ 也會越大 或者 當

$x$ 越大

$f(x)$ 也會越小

圖源: https://manabitimes.jp/math/1289

想當然一個排序好的陣列，或是說一個序列也會具有單調性
除此之外，像是坐標系、時間軸、走訪起來有序的樹狀資料結構…等等，也可能具有單調性，可以試試二分搜尋法

二分搜尋法的限制

• 二分搜尋法的時間複雜度是
  $O(logn)$
• 如果不符合單調性，就無法執行二分搜尋法，所以要記得先排序過
• 值得注意的是，快速排序法的複雜度大概是
  $O(nlogn)$
  因此排序 + 二分搜的複雜度也是
  $O(nlogn)$

如果發現要搜尋的東西不是具有單調性的函數，而是一個具有「極值」的拋物線函數，那麼就可以使用三分搜尋法

C++ 內建二分搜尋法

C++ 其實有內建的二分搜尋法，分別是 lower_bound 與 upper_bound
在比賽時也比較推薦使用這兩個函數，可以省去很多 debug 時間

lower_bound()

lower_bound() 函數可以找到一有序陣列中第一個「大於或等於」目標值的記憶體位置
如果要找的數大於所有的數字，則回傳陣列末尾

由於是找記憶體位置，所以實作時要記得檢掉原本陣列

$[0]$ 的位置

範例1:

int arr[7] = {1, 4, 8, 13, 42, 89, 101};
int target = 42, ans;
ans = lower_bound(arr, arr + 7, target) - arr; // 記得減 arr
cout << target << " 在陣列位置: " << ans << endl;
// arr 對於 C/C++ 而言其實是陣列位置

輸出1:

42 在陣列位置: 4

範例2:

int arr[7] = {1, 4, 8, 13, 42, 89, 101};
int target = 500, ans;
ans = lower_bound(arr, arr + 7, target) - arr; // 記得減 arr
cout << target << " 在陣列位置: " << ans << endl;

輸出2:

500 在陣列位置: 7

---

upper_bound()

upper_bound() 函數可以找到一有序陣列中第一個「大於」目標值的記憶體位置
用法與 lower_bound() 雷同

範例:

int arr[7] = {1, 4, 8, 13, 42, 89, 101};
int target = 42, ans;
ans = upper_bound(arr, arr + 7, target) - arr; // 記得減 arr
cout << target << " 在陣列位置 + 1: " << ans << endl;

輸出:

42 在陣列位置 + 1: 5

例題說明

來源: 2019-2020 ACM-ICPC Brazil Subregional Programming Contest Problem M

題目

這題要吃爆米花，共

$C$ 人分享

$N$ 桶爆米花，每人每一秒只能吃

$T$ 粒爆米花
告訴你第

$i$ 桶有

$P_i$ 粒爆米花，並且要符合以下規則:

• 每個人要挑選「連續」的幾桶爆米花吃
• 一桶爆米花只能被同一人吃完

問他們最快要花多少時間才能吃完所有爆米花

限制

• $1\le N,C\le {10}^5$
• $1\le T\le 50$
• $1\le P_i\le {10}^4$

題解

首先，由於每個人要選擇「連續」的爆米花桶
因此可以發現這其實就是把這

$N$ 桶爆米花分割成

$C$ 個區間

測資一就是這樣切割:

我們可以來觀察一下:

• 根據輸出結果，因為每秒吃

  $4$ 粒爆米花，如果花
  $4$ 秒的時間，每個人各自可以吃
  $16$ 粒
  這樣分割區間的話，三個人分別要吃
  $13$、
  $13$、
  $7$ 粒爆米花，時間絕對來的及

• 試著想想看，如果今天給這三人

  $5$ 秒的時間，可以怎麼分割區間呢?
  因為每秒吃
  $4$ 粒爆米花，如果花
  $5$ 秒的時間，每個人各自可以吃
  $20$ 粒
  這樣分割區間的話三個人分別要吃
  $16$、
  $17$、
  $0$ 顆
  會發現這樣有人沒分到，所以是
  $2$ 個區間

• 試著想想看，如果今天給這三人

  $3$ 秒的時間，可以怎麼分割區間呢?
  因為每秒吃
  $4$ 粒爆米花，如果花
  $3$ 秒的時間，每個人各自可以吃
  $12$ 粒
  這樣分割區間的話三個人分別要吃
  $5$、
  $11$、
  $10$ 顆，剩下
  $7$ 顆吃不完
  會發現這樣會有
  $4$ 個區間(不是我要的答案)

可以歸納出三點:

• 當我代入越大的時間，分割區間越少塊
• 當我代入越小的時間，分割區間越多塊
• 代入的時間最少
  $1$ 秒，最多
  $\sum Pi$ 秒 (即所有爆米花一人獨享)
  寫成不等式:
  $1\le \mathrm{代}\mathrm{入}\mathrm{的}\mathrm{時}\mathrm{間}\le \sum Pi$

可以發現子結論 具有單調性!!!

因此只要對時間做二分搜尋
每次搜尋確定可以分割的塊數小於或等於人數 (小於的話就是有人分

$0$ 粒)，就記錄答案

程式實作

int check(int x){
    x *= t; // 算每人各可以吃幾粒
    int cut = 1, total = 0;
    for(int i = 0; i < n; i++){ // 找的貪心一點
        if(pc[i] > x)   // 如果這桶爆米花比我能吃的總數還多
            return 1e9; // 那就我就算分割無限多塊也吃不完
        if(total + pc[i] <= x)
            total += pc[i];
        else // 多增加一個區間
            total = pc[i], cut++;
    }
    return cut;
}

signed main(){
    /*****略*****/
    int l = 1, r = 1e9 / t, mid;
    while(l <= r){
        mid = (l + r) / 2;
        int x = check(mid);
        if(x <= c)
            r = mid - 1, ans = mid; // 記得紀錄答案
        else
            l = mid + 1;
    }
    /*****略*****/
}

PS : 根據經驗法則，有時候二分搜尋也有可能是一種「逼近」答案的技巧

題目練習

二分搜尋法是 APCS 的常客喔

Zerojudge c575. APCS 2017-0304-4基地台
Zerojudge d732. 二分搜尋法 (裸題)
ABC 231_C Counting 2 (可以想成裸題)
Zerojudge f581. APCS 3. 圓環出口 (前綴和 + 二分搜)
Zerojudge i401. APCS 3. 雷射測試
CSES Concert Tickets (資料結構 + 二分搜)
LeetCode First Bad Version (猜數字裸題)
LeetCode Find the Duplicate Number (其實可以不需要二分搜，但是題目要)
CSES Factory Machines (對時間二分搜)
ABC 319_D Minimum Width (可以轉化成例題的區間分割問題)
CSES Array Division
CSES Sum of Three Values (排序 + 窮舉 + 二分搜)
LeetCode Koko Eating Bananas (用二分搜猜速率)

---

參考資料

• 海大競程 - search algorithm & 實作misc
• geeksforgeeks - Binary Search Algorithm – Iterative and Recursive Implementation

---

ShanC 程式競賽筆記
作者: ShanC
更新: 2024/10/4 (颱風天寫的)