###### tags: `MDCPP` #### MDCPP進階組講義04 ## 二分搜 Binary Search 作者：LittlePants ---- ## 何謂二分搜 - 就是每次都把搜尋區間縮小一半的搜尋方式 ---- ## 例題 - 給你一個長度為N的已排序陣列，要你找出大於等於x的第一個數 ---- ## 方法1 - 把陣列從頭到尾掃一遍 - 複雜度 $O(n)$ ---- ## 方法2 - 既然都給了以排序的陣列，那就可以好好利用它的性質 - 使用二分搜 複雜度$O(logN)$ ---- ## 思考 - 對於每個在陣列裡的數，他不是大於等於x，就是小於x - 雖然聽起來像幹話，但轉化一下就變成 ---- - 如果陣列中這個數字小於x，那x就一定在他右邊 - 反之x就會在這個數左邊或這個數就是x ---- - 我們可以善用這個性質 - 每次都先用搜索區間的中點進行判斷 - 就可以將搜索範圍減少一半 ---- ## 實作練習 - 我們來用程式把二分搜打出來(記得如果題目沒排序的話要先排序) ---- ```cpp= int bs(int x){ // x 是我們要找的數字 // 假設題目給的陣列存在 a[] 長度為 n int l = 1, r = n; // 假設數列存在 a[1] ~ a[n] while(l < r){ int mid = (l+r)/2; // 區間中點 if(a[mid] < x) l = mid + 1; // x 在 mid 的右邊 所以範圍變為右半邊 else r = mid; // x 在 mid 的左邊 } return a[l]; } ``` --- ## STL函式教學 ---- ## lower_bound / upper_bound - lower_bound(x)可以取出陣列中大於**等於**x的第一個數 - upper_bound(x)則是取出陣列中大於x的第一個數 - 兩個函式都是回傳指向那個數的指標(或迭代器) ---- ## 用法 ```cpp= int a[100], n, x; int main(){ cin>>n>>x; for(int i = 0; i < n; i++) cin>>a[i]; sort(a, a+n); auto ptr = lower_bound(a, a+n, x); // lower_bound(first, last, goal); //放入要搜尋的範圍 和 要搜尋的值 cout << *ptr << '\n'; } ``` vector也有這個功能，但以前教過了這裡便不多說 ---- ## 小問題 - 如何找到小於x最大的數? ---- ```cpp= auto ptr = prev(lower_bound(a, a+n, x)); ``` --- ## 小練習 ---- ## [CF 706B Interesting drink](https://codeforces.com/problemset/problem/706/B) 大家練習下英文吧 ---- 這邊有翻譯 大家可以先不要點開來看 :::spoiler 題目給你一個陣列和q個數字 要分別輸出這q個數字大於等於陣列裡的幾個數字 ::: ---- ---- ## 思考 - 如果每次都掃描一遍陣列 時間複雜度$O(QN)$ - 很明顯會超時 ---- 我們改成用二分搜 首先要先排序陣列 時間複雜度$O(NlogN)$ 在對每個詢問使用二分搜 複雜度$O(QlogN)$ ### 總複雜度$O((Q+N)logN)$ ---- ### 小提醒 提醒一下大家不要太過依靠stl函式 因為有些題目一定要用自己寫的二分搜(等下會教) 所以大家一定要練習自己寫看看 --- ## 進階用法 ---- ## 對答案二分搜 ---- ## 甚麼是對答案二分搜? 就是在答案的範圍內用二分搜去猜解答案 ---- ## 例題 終極密碼 電腦會在1 - 100000 的區間內選一個數字 你要用最少的次數猜出電腦選的數字 每次猜完後電腦會回答你 biger,lower和yes 分別代表你的猜測 大於這個數字/小於這個數字/猜對了 ---- ## 思考 很明顯這一題我們可以對答案範圍(1 - 100000) 進行二分搜 因為這題的答案具有單調性 ---- 甚麼是單調性呢? 就是我們先選一個數 然後可以判斷出答案會比這個數小 還是比這個數大 因此我們可以決定搜索區間要變成左半邊或右半邊 ---- ## [TIOJ 1044](https://tioj.ck.tp.edu.tw/problems/1044) 這題是互動題 跟例題有87%像 有興趣的同學可以寫寫看 ---- ## 例題二 ---- ## [MDCPP 基地台(APCS201703)](http://mdcpp.mingdao.edu.tw/problem/AP014) 請大家閱讀一下題目 ---- 對答案二分搜通常會跟貪心算法結合在一起 雖然我們還沒有教過 但貪心其實就是個很直覺的東西 大家應該可以很好理解 ---- ## 思考 首先我們先把P陣列排序 然後我們知道 答案的範圍會在 $1 \sim (P[N-1] - P[0])$之間 ---- 然後再想一下我們的貪心策略 解如我們選定了一個直徑 R ---- 我們從左到右遍歷所有服務點 當我們遇到了一個沒被覆蓋的服務點 P[i] 我們一定要覆蓋他 所以我們可以用將基地台的最左端對齊這個點 所以我們可以覆蓋到 P[i] ~ P[i] + R ---- 這樣我們就可以求出當直徑為R時 至少要多少個基地台 然後可以依據需要的基地台數大於 K 或 小於 K 作為二分搜的依據 ---- 二分搜複雜度 $O(log 10^9)$ 大約等於 30 排序複雜度 $O(NlogN)$ 遍歷複雜度 $O(N)$ ## 總複雜度$O(NlogN + Nlog10^9)$ ---- 參考code :::spoiler ```cpp= #include<bits/stdc++.h> #define ft first #define sc second #define all(x) (x).begin(),(x).end() #define sz(x) (int)(x).size() #define mem(x,val) memset(x,val,sizeof x) #define pii pair<int,int> #define pb emplace_back #define ar array #define int long long #define wopen(x) freopen((x),"w",stdout) #define ropen(x) freopen((x),"r",stdin) #define mid (l+r>>1) using namespace std; int n, k, l, r, p[50005]; bool check(int x){ int c = p[0] + x - 1, cnt = 1; for(int i = 1; i < n; i++){ if(p[i] > c) cnt++, c = p[i] + x; } return cnt <= k; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> k; for(int i = 0; i < n; i++){ cin >> p[i]; r = max(p[i], r); } l = 1; sort(p, p + n); while(l < r){ if(check(mid)){ r = mid; } else { l = mid+1; } } cout << l << '\n'; } ``` ::: --- ## 回家練習 ---- [NPSC 零](http://mdcpp.mingdao.edu.tw/problem/C032) 有用到一點數學觀念大家可以想想看 ---- [夏綠蒂的回家作業](http://mdcpp.mingdao.edu.tw/problem/A051) 二分搜的應用 是一個蠻重要的觀念 ----