# 二分搜 # Binary search ---- ## 搜尋演算法 ---- ## 循序搜尋 O(N) ## 二元樹 O(N) ~ O(Log2N) ## 二分搜 O(Log2N) ## 內插搜尋法 略優於 O(Log2N) ## 雜湊法(hashing) O(1) ---- ### 給你一個單調序列和裡面的某個值 ### 求該值在序列裡的index ---- ## 單調序列? #### 如果該序列為嚴格遞增或遞減即為單調序列 ---- ## 嚴格遞增? ## 後一項恆大於等於前一項 ---- ## 嚴格遞減? ## 後一項恆小於等於前一項 ---- # 範例 ---- #### 給一個由小到大排序好且長度為 10 的陣列arr #### 請問數字 48 在陣列的第幾格?(保證答案唯一)  ---- ### 因為我們確定arr[i]<=arr[i+1] ### arr[i]>=arr[i-1] ### 所以只要知道arr[i]跟目標的關係 ### 就能確定答案不在arr[i]以前或以後 ---- ## 二分搜的精神 ## 每次逐一砍半 ---- ## left = 0, right = 9 ## mid = (0+9)/2 = 4  ---- ## 因為 arr[mid] < 48 ## 所以可以確定 arr[0]~arr[mid] ## 都不會有答案 ## 因此把新的left定在mid+1 ---- ## left = 5, right = 9 ## mid = (5+9)/2 = 7  ---- ## arr[mid] > 48 ## 所以可以確定 arr[mid]~arr[9] ## 都不會有答案 ## 因此把新的right定在mid-1 ---- ## left = 5, right = 6 ## mid = (5+6)/2 = 5  ---- ## left = 6, right = 6 ## mid = (6+6)/2 = 6  ---- ```cpp= #include<iostream> using namespace std; int arr[10] = {3, 12, 14, 20, 29, 32, 48, 49, 63, 71}; int target = 48; int main(){ int l = 0, r= 9, mid; while(l<r){ mid = (l+r)/2; if(arr[mid]<target) l = mid+1; else if(arr[mid]>target) r = mid-1; else break; } mid = (l+r)/2; cout << mid << '\n'; } ``` ## code ---- ## 練習題 ## CSDC #65 ---- # ans ```cpp= #include<iostream> using namespace std; int main(){ int n, m; cin >> n >> m; int arr[n]; for(int i = 0; i < n; i++){ cin >> arr[i]; } while(m--){ int tar; cin >> tar; int l = 0, r = n-1, mid; while(l<r){ mid = (l+r)/2; if(arr[mid]>tar) r = mid-1; else if(arr[mid]<tar) l = mid+1; else break; } mid = (l+r)/2; cout << mid+1 << '\n'; } } ``` ---- ## 排序小幫手 std::sort ```cpp= #include<iostream> #include<vector> #include<algorithm> // std::sort using namespace std; int arr[4] = {3, 1, 7, 2}; vector<int> v = {3, 5, 1, 4, 9, 8, 7}; int main(){ sort(arr, arr+4); // {1, 2, 3, 7} sort(v.begin(), v.end()); // {1, 3, 4, 5, 7, 8, 9} } ``` --- ## 二分搜沒那麼簡單 ---- ## 例一: ### 有一陣列，求大於X的最小值 ---- ## X可能不在陣列中 ## 或者有多個X在陣列中 ## 這時就需要稍微修改一下二分搜 ---- ```cpp= int l = 最小的可能答案; int r = 最大的可能答案; //搜arr[10], r = 10 (why?) int mid; while(l<r){ mid = (l+r)/2; if(arr[mid]<=x) l = mid+1; else{ //arr[mid] 不小於等於x r = mid; //此時的mid有可能是答案 //因為不確定後面會不會搜到比他更小的且滿足條件的元素 //所以先不剔除他 } } //迴圈結束後，l=r=答案 ``` ---- ## 值得注意的是 ## 此迴圈在l=r時就會break ## 因此mid永遠不會等於r ## 所以不用擔心overflow的問題 ---- ## 例二: ## 有一陣列，求小於等於X的最大值 ---- ## 思考一下 ## 例一求出了大於X的最小值 ## 那麼他的前一個元素即為所求 ---- ## 記得檢查是否有搜到 ## (是否至少有一元素滿足條件) ## 如果沒有l和r會等於一開始的r ---- ### 聰明的你應該可以舉一反三 ### 知道如何求出大於等於X的最小值 ### 和小於X的最大值 --- ## 聽沒有很懂? ### 接下來講的東西可能對你很有幫助 ---- ## std::upper_bound() ## 用於找出找出陣列(vector)內 ## 第一個大於目標的指標(iterator) ---- ## 語法 ### upper_bound(最小可能,最大可能,目標) ---- ### array ```cpp= int arr[10] = {1, 3, 4, 6, 9, 10, 13, 19, 22, 43}; int *a = upper_bound(arr, arr+10, 13); //include<algorithm> cout << *a << " " << a-arr; // 19 7; //若a=arr+10即為沒搜到 ``` ### vector ```cpp= vector<int> v(10) = {1, 3, 4, 6, 9, 10, 13, 19, 22, 43}; int *a = upper_bound(v.begin(), v.end(), 13); //include<algorithm> cout << *a << " " << a-v.begin(); // 19 7; //若a=v.end()即為沒搜到 ``` ---- ### std::lower_bound() ### 用於找出找出陣列(vector)內 ### 第一個不小於目標的指標(iterator) ---- ## 語法 ### lower_bound(最小可能,最大可能,目標) ---- ### array ```cpp= int arr[10] = {1, 3, 4, 6, 9, 10, 13, 19, 22, 43}; int *a = lower_bound(arr, arr+10, 13); //include<algorithm> cout << *a << " " << a-arr; // 13 6; //若a=arr+10即為沒搜到 ``` ### vector ```cpp= vector<int> v(10) = {1, 3, 4, 6, 9, 10, 13, 19, 22, 43}; int *a = lower_bound(v.begin(), v.end(), 13); //include<algorithm> cout << *a << " " << a-v.begin(); // 13 6; //若a=v.end()即為沒搜到 ``` ---- ## 練習題 ## CSDC #230 ---- ## ans(手刻二分搜) ```cpp= #include<iostream> using namespace std; int main(){ int n, k; cin >> n >> k; int arr[n]; for(int i = 0; i < n; i++){ cin >> arr[i]; } int ans1, ans2; int l = 0, r = n, mid; while(l<r){ //大於等於k的最小值 mid = (l+r)/2; if(arr[mid]<k) l = mid+1; else r = mid; } if(l==n){ //沒有元素大於等於k cout << 0 << '\n'; return 0; } ans1 = l; l = 0; r = n; while(l<r){ //不大於k的最大值(第一個大於k的位置-1) mid = (l+r)/2; if(arr[mid]<=k) l = mid+1; else r = mid; } if(l==0){ //所有元素都大於k cout << 0 << '\n'; return 0; } ans2 = l-1; cout << ans2-ans1+1 << '\n'; } ``` ---- ## ans(upper/lower bound) ```cpp= #include<iostream> #include<vector> #include<algorithm> using namespace std; int main(){ int n, k; cin >> n >> k; vector<int> v(n); for(int i = 0; i < n; i++) cin >> v[i]; vector<int>::iterator right = upper_bound(v.begin(), v.end(), k); auto left = lower_bound(v.begin(),v.end(), k); if(left==v.end()||right==v.end()){ cout << 0 << '\n'; return 0; } int ans1 = left-v.begin(); int ans2 = right-1-v.begin(); cout << ans2-ans1+1 << '\n'; } ``` ---- ## 即使bound看起來很好用 ## 還是不行太依賴他 ---- ## 鐵板 ## apcs近年來很喜歡出的題型 ## greedy+二分搜 ---- ## 某年的實作第四題: ### 有排每塊木板高度不一的柵欄 ### 還有一些寬度不一的海報 ### (海報高度皆為1) ### 欲使每張海報貼到高度相同的位置 ### 求最大高度 ----  ---- ## 條件:每張海報能夠順利貼上去 ## 對高度二分搜 ## 找出能夠滿足條件的最大高度 ## l = 1, r = max(木板高度)+1 ---- ### 這時會發現bound在這邊毫無用武之地 ### 最終還是得寫出二分搜結構 ### 並慢慢驗證能否滿足條件 ---- # ZJ #h084 ## 題解網路上應該一堆