二分搜 - HackMD

二分搜 === ---- ## 什麼是二分搜? ---- 一種快速的在資料中尋找所要的資料的方法 --- 在介紹他之前先講一個小遊戲 ---- ### 猜數字一個人想1~100中的一個數字另一個人不斷地猜數字職猜中為止想數字的人只會回答 __比答案大__ 或 __比答案小__ 及 __猜中__ ---- 怎麼樣猜得最快? 從1一個一個猜到100? X  **每次都猜中間值!** ---- 我們來看看為什麼那是最快的 假設答案是82 那我們就會猜 _50_ , _87_ , _68_ , _77_ , _82_ , 花了五次就找到了答案 而從1開始找則會花82次才能找到 ---- #### 來分析一下時間複雜度先來看第一個方法從1開始找 對他來說最糟的情況就是目標在n 1到n會跑N次所以時間複雜度是O(N) ---- 接下來我們來看用中間值去找的方法: 因為每次要找的範圍都會除2 所以最糟的情況下 2$^{k}$=n k=log(N) 所以時間複雜度是O(log(N)) --- ### 這樣的演算法就叫「二分搜尋法」利用這項演算法我們可以在「有序陣列」中以O( log(N) ) )的複雜度找到目標 ---- 實際上要怎麼寫? ---- 我們有3種寫二分搜的方法 第1個是用一個while迴圈不斷移動左界和右界來找目標 第2個是用for迴圈一段一段往前跳 第3個則是用內建的STL 接下來會一一列出程式碼說明 --- 我們利用這個例題來解釋 ``` 給一個長度N的陣列，進行M次詢問K，請輸出陣列中大於K的最小值 N,M<1e5,陣列的值及k<1e9 ``` ---- 先來分析複雜度如果直接用一個一個找的話複雜度會是 __O(NM)__ 很明顯不行這時候就要用二分搜了 ---- 利用二分搜我們會需要先排列這個陣列 排列的複雜度是O( Nlog(N) ) 而搜尋m次每次的複雜度都是O( log(N) ) 所以搜尋的部分就是O( Mlog(N) ) 整個的複雜度就是max( Nlog(N) , Mlog(N) ) ) ---- 看起來時間是不會爆的那我們就可以開始寫了 --- ### 用while的方法： ```cpp= #include<bits/stdc++.h> using namespace std; #define int long long const int N=1e5+5; int n,m,k,arr[N]; signed main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>arr[i]; sort(arr+1,arr+n+1);//排列 arr[n+1]=-1; //找不到時回傳-1 for(int i=1;i<=m;i++){ cin>>k; int l=1,r=n+1,mid;//初始化左界、右界、中點、左閉右開 while(l<r){ //當在正常範圍時重複: mid=(l+r)/2; //計算中點(注意無條件捨去會偏左) if(arr[mid]>k){ //當k在mid的左邊時: r=mid; //將右界移到mid }else{ l=mid+1; //否則把右界移到mid+1 } } cout<<arr[l]<<"\n"; } return 0; } ``` ---- ### 用跳的找 ```cpp= #include<bits/stdc++.h> using namespace std; #define int long long const int N=1e5+5; int n,m,k,arr[N]; signed main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>arr[i]; sort(arr+1,arr+n+1);//排列 arr[n+1]=-1; //找不到時回傳-1 for(int i=1;i<=m;i++){ cin>>k; int w=0; for(int jump=n;jump>0;jump/=2){ //注意要用while不是if while(w+jump<=n and arr[w+jump]<=k){ w+=jump; } } cout<<arr[w+1]<<"\n"; //w會停在最大<=k的地方，所以要加1 } return 0; } ``` ---- ### 用STL ```cpp= #include<bits/stdc++.h> using namespace std; #define int long long const int N=1e5+5; int n,m,k,arr[N]; signed main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>arr[i]; sort(arr+1,arr+n+1);//排列 arr[n+1]=-1; //找不到時回傳-1 for(int i=1;i<=m;i++){ cin>>k; int ans=*upper_bound(arr+1,arr+1+n,k); cout<<ans<<"\n"; } return 0; } ``` --- ### 二分搜習題 [MD Judge A051](http://mdcpp.mingdao.edu.tw/problem/A051) [MD Judge B029](http://mdcpp.mingdao.edu.tw/problem/B029) [MD Judge B051](http://mdcpp.mingdao.edu.tw/problem/B051) --- ### 外掛二分搜外掛二分搜就是把判斷要往左往右找的條件式另外寫一個bool函式通常執行一次bool函式時間複雜度會是$O(N)$ 整體會是$O(NlogN)$ ---- 例題 [恢復能量的白雲熊膽丸](http://mdcpp.mingdao.edu.tw/problem/AP015) ---- 這題比較簡單的想法是把F從1一直跑到$10^{10}$ 只要滿足條件就break出來輸出F 這樣做不用算時間複雜度一定爆我們可以觀察到當F越大需要嗑藥的次數就越少是 __有序的__ 所以我們就能夠用外掛二分搜解決這題 ---- code ```cpp= #include<bits/stdc++.h> using namespace std; #define int long long const int N=1e5+5; int n,m,p[N]; bool check(int f){ int power=f; int cnt=0; for(int i=1;i<=n;i++){ if(p[i]>f) return 1; if(power<p[i]){ power=f; cnt++; } power-=p[i]; } if(cnt>m) return 1; else return 0; } signed main(){ ios::sync_with_stdio(0);cin.tie(0); cin>>n>>m; for(int i=1;i<=n;i++) cin>>p[i]; int ans=0; p[0]=0; for(int jump=1e15;jump>0;jump/=2){ while(check(ans+jump)){ ans+=jump; } } cout<<ans+1; } ``` ---- ### 練習題 [基地台](http://mdcpp.mingdao.edu.tw/problem/AP014)