二分搜尋法 - HackMD

# 二分搜尋法 Binary Search 如何在一堆東西裡面尋找我想要的東西呢?相向大家都有相似的疑問吧? 這章節會介紹兩個常用的搜尋演算法 ## 線性搜尋法 Linear Search 找東西最直觀的方法就是把所有東西掃過一遍，這樣就可以找到想要的內容了而這種方法就叫做線性搜尋法線性搜尋法很簡單，對於一個陣列，只需要一個一個比較是否相同即可 ```cpp 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. 發現紅線剛好在中線上(結束!!) {%youtube kBncwQWVcj8 %} --- ### 舉例假設有一陣列 $arr[7] = \{1, 4, 8, 13, 42, 89, 101\}$，目標是希望找到 $42$ 在這其中，我們可以使用三個指針 $L, M, R$ 來維護 {%youtube oxuBieClpi4 %} --- ### 實作二分搜尋法需要先準備好一個「有序」的序列與一個目標值最後會回傳目標值在序列中的位置 ```cpp 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; } ``` 詳細流程如下: ```mermaid flowchart TD st[宣告左界 l = 0、右界 r = n-1]:::declear cnd{l <= r}:::condition dp1["宣告 m = (l + r) / 2"]:::declear cnd1{"arr[m] 等於目標"}:::if cnd2{"arr[m] 小於目標"}:::if cnd3{"arr[m] 大於目標"}:::if c1["找到答案"]:::st c5["離開迴圈"]:::st c4["沒找到答案"]:::st c2["l = m + 1"]:::st c3["r = m - 1"]:::st c4 --> c5 c1 --> c5 cnd -->|No| c4 st --> cnd --> |Yes| dp1 dp1 --> cnd1 dp1 --> cnd2 dp1 --> cnd3 cnd1 --> c1 cnd2 --> c2 --> cnd cnd3 --> c3 --> cnd classDef declear stroke:#00f, fill:#fff classDef condition stroke:#0f0, fill:#fff classDef if stroke:#f00, fill:#fff classDef st stroke:#000, fill:#fff ``` PS : 實作時如果遇到無限迴圈，可以檢查是否維護好邊界或是終止條件 ## 單調性二分搜尋法基本上符合單調性的任何東西都可以使用單調性基本上就是對於一個函數 $f(x)$: 當 $x$ 越大 $f(x)$ 也會越大或者當 $x$ 越大 $f(x)$ 也會越小 <img src="https://res.cloudinary.com/bend/f_auto/shikakutimes/s3/bend-image/1645534943.png" style="margin: 0 auto; display: block; width: 400px"> 圖源: <a href="https://manabitimes.jp/math/1289">https://manabitimes.jp/math/1289</a> 想當然一個排序好的陣列，或是說一個序列也會具有單調性除此之外，像是坐標系、時間軸、走訪起來有序的樹狀資料結構...等等，也可能具有單調性，可以試試二分搜尋法 ## 二分搜尋法的限制 - 二分搜尋法的時間複雜度是 $O(log~n)$ - 如果不符合單調性，就無法執行二分搜尋法，所以要記得先排序過 - 值得注意的是，快速排序法的複雜度大概是 $O(n~log~n)$ 因此排序 + 二分搜的複雜度也是 $O(n~log~n)$ 如果發現要搜尋的東西不是具有單調性的函數，而是一個具有「極值」的拋物線函數，那麼就可以使用[三分搜尋法](https://hackmd.io/@ShanC/ternary-search) ## C++ 內建二分搜尋法 C++ 其實有內建的二分搜尋法，分別是 `lower_bound` 與 `upper_bound` 在比賽時也比較推薦使用這兩個函數，可以省去很多 debug 時間 ### lower_bound() lower_bound() 函數可以找到一有序陣列中第一個「大於或等於」目標值的記憶體位置如果要找的數大於所有的數字，則回傳陣列末尾由於是找記憶體位置，所以實作時要記得檢掉原本陣列 $[0]$ 的位置 #### 範例1: ```cpp 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: ```cpp 42 在陣列位置: 4 ``` #### 範例2: ```cpp 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: ```cpp 500 在陣列位置: 7 ``` --- ### upper_bound() upper_bound() 函數可以找到一有序陣列中第一個「大於」目標值的記憶體位置用法與 `lower_bound()` 雷同 #### 範例: ```cpp 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; ``` #### 輸出: ```cpp 42 在陣列位置 + 1: 5 ``` ## 例題說明來源: [2019-2020 ACM-ICPC Brazil Subregional Programming Contest Problem M](https://codeforces.com/gym/102346/problem/M) ### 題目這題要吃爆米花，共 $C$ 人分享 $N$ 桶爆米花，每人每一秒只能吃 $T$ 粒爆米花告訴你第 $i$ 桶有 $P_{i}$ 粒爆米花，並且要符合以下規則: - 每個人要挑選「連續」的幾桶爆米花吃 - 一桶爆米花只能被同一人吃完問他們最快要花多少時間才能吃完所有爆米花 ### 限制 - $1 \leq N,C \leq 10^{5}$ - $1 \leq T \leq 50$ - $1 \leq P_{i} \leq 10^{4}$ ### 題解首先，由於每個人要選擇「連續」的爆米花桶因此可以發現這其實就是把這 $N$ 桶爆米花分割成 $C$ 個區間測資一就是這樣切割: <img src="https://hackmd.io/_uploads/SJRjo7NGJl.png" style="margin: 0 auto; display: block; width: 400px"> 我們可以來觀察一下: - 根據輸出結果，因為每秒吃 $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 P{i}$ 秒 (即所有爆米花一人獨享) 寫成不等式: $1 \leq 代入的時間\leq \sum P{i}$ 可以發現子結論 **具有單調性!!!!!** 因此只要對**時間**做二分搜尋每次搜尋確定可以分割的塊數**小於或等於**人數 (小於的話就是有人分 $0$ 粒)，就記錄答案 ### 程式實作 ```cpp 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基地台](https://zerojudge.tw/ShowProblem?problemid=c575) [Zerojudge d732. 二分搜尋法](https://zerojudge.tw/ShowProblem?problemid=d732) (裸題) [ABC 231_C Counting 2](https://atcoder.jp/contests/abc231/tasks/abc231_c?lang=en) (可以想成裸題) [Zerojudge e616 Aggressive cows](https://zerojudge.tw/ShowProblem?problemid=e616) [Zerojudge f581. APCS 3. 圓環出口](https://zerojudge.tw/ShowProblem?problemid=f581) (前綴和 + 二分搜) [Zerojudge i401. APCS 3. 雷射測試](https://zerojudge.tw/ShowProblem?problemid=i401) [CSES Concert Tickets](https://cses.fi/problemset/task/1091/) (資料結構 + 二分搜) [LeetCode First Bad Version](https://leetcode.com/problems/first-bad-version/description/) (猜數字裸題) [LeetCode Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/description/) (其實可以不需要二分搜，但是題目要) [CSES Factory Machines](https://cses.fi/problemset/task/1620) (對時間二分搜) [ABC 319_D Minimum Width](https://atcoder.jp/contests/abc319/tasks/abc319_d?lang=en) (可以轉化成例題的區間分割問題) [CSES Array Division](https://cses.fi/problemset/task/1085) [CSES Sum of Three Values](https://cses.fi/problemset/task/1641) (排序 + 窮舉 + 二分搜) [LeetCode Koko Eating Bananas](https://leetcode.com/problems/koko-eating-bananas/description/) (用二分搜猜速率) ---- ## 參考資料 - [海大競程 - search algorithm & 實作misc](https://hackmd.io/@LeeShoWhaodian/Byyg2J6byl#/) - [geeksforgeeks - Binary Search Algorithm – Iterative and Recursive Implementation](https://www.geeksforgeeks.org/binary-search/) ---- > [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC) > 作者: ShanC > 更新: 2024/10/4 (颱風天寫的)