Search Algorithms

# Search Algorithms By Colin --- ## What is search algorithm? - 在資料中尋找特定元素的演算法 - 例如： - 尋找3是否在 5 1 7 2 9 4 3 8 6 中 - 尋找3在 5 1 7 2 9 4 3 8 6 中的位置 - 尋找在 1 3 5 7 9 中比6大的最小值 - 尋找 5 1 7 2 9 4 3 8 6 中第3大的元素 --- ## Linear Search 線性搜尋 - 又稱暴搜、窮舉 - 逐⼀檢查資料集合中的每個項⽬，直到找到⽬標項⽬ - 時間複雜度：$O(n)$ ---- Example 1: 尋找3是否在陣列 int arr[9]={5,1,7,2,9,4,3,8,6} 中 ```cpp= #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; signed main(){ int arr[9]={5,1,7,2,9,4,3,8,6}; bool ans=0; for(int i=0;i<9;i++){ if(arr[i]==3){ ans=1; break; } } if(ans) cout<<"Yes\n"; else cout<<"No\n"; return 0; } ``` ---- Example 2: 尋找3在陣列 int arr[9]={5,1,7,2,9,4,3,8,6} 中的位置 ```cpp= #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; signed main(){ int arr[9]={5,1,7,2,9,4,3,8,6}; int index; for(int i=0;i<9;i++){ if(arr[i]==3){ index=i; break; } } cout<<index<<'\n'; return 0; } ``` ---- Example 3: [CSDC246 不擅長出題的社長](https://csdc.tw/problem/246/) ---- 題解： - 想法：用兩層for迴圈窮舉$t$和$q$，再判斷$k-a\times t-b\times q$是否整除$c$，即可得知是否為一組解 - 窮舉的範圍：因為$k,a,b,c,t,q,r$皆為非負整數，所以$a\times t\le k$，$t$只需窮舉到$\lfloor \frac{k}{a}\rfloor$，同理，$a\times t+b\times q\le k$，$q$只需窮舉到$\lfloor \frac{k-a\times t}{b}\rfloor$ - 注意：$k=0$時，若透過上述方法窮舉，$t$,$q$,$r$會皆為$0$，不符合要求，所以需特別判斷 ---- AC code ```cpp= #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; signed main(){ int n,k,a,b,c; cin>>n; while(n--){ int ans=0; cin>>k>>a>>b>>c; if(k==0){ cout<<"No solution exists\n"; continue; } for(int t=0;t<=(k/a);t++){ for(int q=0;q<=(k-a*t)/b;q++){ if((k-a*t-b*q)%c==0){ int r=(k-a*t-b*q)/c; cout<<t<<' '<<q<<' '<<r<<'\n'; ans=1; break; } } if(ans) break; } if(!ans) cout<<"No solution exists\n"; } return 0; } ``` --- ## Binary Search 二分搜尋 - 簡稱二分搜 - ⽤於有序資料(具有單調性的資料)的搜尋⽅法 - 反覆將搜尋範圍縮⼩⼀半，通過比較⽬標值與中間元素的⼤⼩，來判斷⽬標值可能在資料的哪⼀半 - 時間複雜度：$O(log_2\ n)$ ---- 變數假設： $n$: 資料數量 $x$: 目標數值 $left$: 目前處理的資料左界的編號，初始化為$0$ $right$: 目前處理的資料右界的編號，初始化為$n-1$ $mid$: 左界與右界的中間 ---- $mid=(left+right)/2$ //資料總數較大時$(left+right)$可能會overflow $mid=left+(right-left)/2$ //Better ---- $n=10$，$x=48$ $left=0，right=9$ $mid=0+(9-0)/2=4$ ![](https://i.imgur.com/W3cL56m.png) 因為$x>arr[mid]$，所以可以將$arr[left]$ ~ $arr[mid]$這段捨去 將$left$修改成$mid+1=5$ ---- $left=5，right=9$ $mid=5+(9-5)/2=7$ ![](https://i.imgur.com/ES1Mcwz.png) 因為$x<arr[mid]$，所以可以將$arr[mid]$ ~ $arr[right]$這段捨去 將$right$修改成$mid-1=6$ ---- $left=5，right=6$ $mid=5+(6-5)/2=5$ ![](https://i.imgur.com/RNoVnER.png) 因為$x>arr[mid]$，所以可以將$arr[left]$ ~ $arr[mid]$這段捨去 將$left$修改成$mid+1=6$ ---- $left=6，right=6$ $mid=6+(6-6)/2=6$ ![](https://i.imgur.com/7FRdPtd.png) $x=arr[mid]$，完成搜尋，得到$x$所在編號為$mid=6$ ---- code ```cpp= #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int BinarySearch(int arr[],int n,int x){ int l=0,r=n-1; while(l<=r){ int mid=l+(r-l)/2; if(x==arr[mid]) return mid; else if(x<arr[mid]) r=mid-1; else l=mid+1; } return -1; } signed main(){ int n,x; cin>>n>>x; int arr[n]; for(int i=0;i<n;i++) cin>>arr[i]; cout<<BinarySearch(arr,n,x)<<'\n'; return 0; } ``` ---- Example 1: [CSDC65 你的日常裡需要抄書](https://csdc.tw/problem/65/) ---- 題解：因為輸入的$N$個數必為有序序列，所以對於每個輸入的$X$，二分搜其在陣列內的位置即可 ---- AC code ```cpp= #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int BinarySearch(int arr[],int n,int x){ int l=0,r=n-1; while(l<=r){ int mid=l+(r-l)/2; if(arr[mid]==x) return mid; else if(x<arr[mid]) r=mid-1; else l=mid+1; } } signed main(){ int n,m; cin>>n>>m; int arr[n+1]; for(int i=1;i<=n;i++) cin>>arr[i]; while(m--){ int x; cin>>x; cout<<BinarySearch(arr,n,x)<<'\n'; } return 0; } ``` ---- Example 2: [CSDC236 (緊急)遙遠的國度需水資源！！！](https://csdc.tw/problem/236/) ---- 題解： 1. 若$m$個容積為$v$的罐子可以容納所有雨水，則$m$個容積大於$v$的罐子必定也可以容納所有雨水（罐子容積大小具有單調性），因此可以對罐子容積大小進行二分搜 2. 二分搜的範圍： - 因為一杯水一定要完整倒入一個罐子，所以罐子容積大小至少要為最大的那杯水的體積 - 罐子容積大小至多為所有杯水的體積和，因為此時就可以容納所有雨水了，再多是浪費空間 ---- 3. 定義test()函數，檢測罐子容積為$v$時需要的罐子數量。若test(v)$\le m$，代表罐子容積為$v$時必定可以容納所有雨水，因此可將$r=mid-1$，往更小的容積檢查；若test(v)$>m$，代表罐子容積為$v$時無法容納所有雨水，因此可將$l=mid+1$，往更大的容積檢查 4. 模擬一下可以知道最終的答案會落在$l$ ---- AC code ```cpp= #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int t,m,n,arr[5005]; int test(int v){ int cnt=1,t=v; for(int i=0;i<n;i++){ if(arr[i]<=t){ t-=arr[i]; }else{ cnt++; t=v-arr[i]; } } return cnt; } int BinarySearch(int l,int r){ while(l<=r){ int mid=l+(r-l)/2; if(test(mid)<=m) r=mid-1; else l=mid+1; } return l; } signed main(){ horaceorz; cin>>t; while(t--){ cin>>m>>n; int maxi=-1,sum=0; for(int i=0;i<n;i++){ cin>>arr[i]; maxi=max(maxi,arr[i]); sum+=arr[i]; } cout<<BinarySearch(maxi,sum)<<'\n'; } return 0; } ``` ---- Example 3: [APCS 2017/03 P4 基地台](https://zerojudge.tw/ShowProblem?problemid=c575) ---- 題解： 1. 若直徑為$R$時可以覆蓋每個點，則直徑大於$R$時必定也可以覆蓋每個點（基地台直徑大小具有單調性），因此可以對直徑大小進行二分搜 2. 二分搜的範圍： - 題目保證最小直徑必然是不小於1的整數，所以直徑至少要為1 - 直徑至多為最遠的兩個點的距離 ---- 3. 定義test()函數，檢測直徑為$R$時需要的基地台數量。若test($R$)$\le k$，代表直徑為$R$時必定可以覆蓋每個點，因此可將$r=mid-1$，往更小的直徑檢查；若test($R$)$>k$，代表直徑為$R$時無法覆蓋每個點，因此可將$l=mid+1$，往更大的直徑檢查 4. 模擬一下可以知道最終的答案會落在$l$ ---- AC code ```cpp= #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int n,k,arr[50005]; int test(int R){ int cnt=1,t=arr[0]; for(int i=1;i<n;i++){ if(arr[i]>t+R){ cnt++; t=arr[i]; } } return cnt; } int BinarySearch(int l,int r){ while(l<=r){ int mid=l+(r-l)/2; if(test(mid)<=k) r=mid-1; else l=mid+1; } return l; } signed main(){ cin>>n>>k; for(int i=0;i<n;i++) cin>>arr[i]; sort(arr,arr+n); int l=1,r=arr[n-1]-arr[0]; cout<<BinarySearch(l,r); return 0; } ``` ---- Example 4: [APCS 2022/01 P4 牆上海報](https://zerojudge.tw/ShowProblem?problemid=h084) ---- 題解： 1. 若高度為$H$時可以張貼所有海報，則高度小於$H$時必定也可以張貼所有海報（高度具有單調性），因此可以對高度進行二分搜 2. 二分搜的範圍： - 最小高度為1 - 最大高度為最高的木板的高度 ---- 3. 定義test()函數，檢測高度為$H$時可以張貼的海報數量。若test($H$)$<k$，代表高度為$H$時無法張貼全部海報，因此可將$r=mid-1$，往更小的高度檢查；若test($H$)$=k$，代表高度為$H$時可以張貼全部海報，因此可將$l=mid+1$，往更大的高度檢查 4. 模擬一下可以知道最終的答案會落在$r$ ---- AC code ```cpp= #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int n,k,h[200005],w[5005]; int test(int H){ int cnt=0,num=0,t=0; for(int i=0;i<n;i++){ if(h[i]>=H){ t++; }else{ while(t>=w[num]){ t-=w[num]; num++; cnt++; if(num==k) return cnt; } t=0; } } while(t>=w[num]){ t-=w[num]; num++; cnt++; if(num==k) return cnt; } return cnt; } int BinarySearch(int l,int r){ while(l<=r){ int mid=l+(r-l)/2; if(test(mid)<k) r=mid-1; else l=mid+1; } return r; } signed main(){ cin>>n>>k; int maxi=-1; for(int i=0;i<n;i++){ cin>>h[i]; maxi=max(maxi,h[i]); } for(int i=0;i<k;i++) cin>>w[i]; int l=1,r=maxi; cout<<BinarySearch(l,r); return 0; } ``` ---- Example 5: [CSDC346 2077](https://csdc.tw/problem/346/) aka 第39屆進階組資格考p5 ---- 題解：我懶得打了(X 很難的二分搜題目去問副社長或是看[**上次資格考的題解**](https://hackmd.io/EOZUB47lSeSiJB6w4eoo6w) ---- AC code ```cpp= #include <iostream> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int Q(int p){ if(p<=100*2) return p/2; else if(p<=100*2+9900*3) return 100+(p-(100*2))/3; else if(p<=100*2+9900*3+990000*5) return 10000+(p-(100*2)-(9900*3))/5; else return 1000000+(p-(100*2)-(9900*3)-(990000*5))/7; } int P(int q){ if(q<=100) return q*2; else if(q<=10000) return 100*2+(q-100)*3; else if(q<=1000000) return 100*2+9900*3+(q-10000)*5; else return 100*2+9900*3+990000*5+(q-1000000)*7; } signed main(){ int A,B; while(cin>>A>>B&&A&&B){ int qx,qy,qsum=Q(A); //f=P(qsum-qx)-P(qx)=B //if(f>B) qx要增加 //if(f<B) qx要減少 int l=0,r=qsum; while(1){ int mid=l+(r-l)/2; if(P(qsum-mid)-P(mid)==B){ qx=mid; break; }else if(P(qsum-mid)-P(mid)>B){ l=mid+1; }else if(P(qsum-mid)-P(mid)<B){ r=mid-1; } } cout<<P(qx)<<'\n'; } return 0; } ``` --- 補充： STL函式 #include\<algorithm> lower_bound() 尋找有序資料大於等於某數的最小值 upper_bound() 尋找有序資料大於某數的最小值 ---- 傳統陣列 ```cpp= int arr[5]={1,3,5,7,9}; auto it1=lower_bound(arr,arr+5,3); //it1會是iterator(記憶體位址) cout<<*it1<<'\n'; //值=3 cout<<it1-arr<<'\n'; //位置=1 auto it2=upper_bound(arr,arr+5,3); //it2會是iterator(記憶體位址) cout<<*it2<<'\n'; //值=5 cout<<it2-arr<<'\n'; //位置=2 ``` ---- vector ```cpp= vector<int> v={1,3,5,7,9}; auto it1=lower_bound(v.begin(),v.end(),3); //it1會是iterator(記憶體位址) cout<<*it1<<'\n'; //值=3 cout<<it1-v.begin()<<'\n'; //位置=1 auto it2=upper_bound(v.begin(),v.end(),3); //it2會是iterator(記憶體位址) cout<<*it2<<'\n'; //值=5 cout<<it2-v.begin()<<'\n'; //位置=2 ``` ---- 用lower_bound()解 Example 1: [CSDC 65](https://csdc.tw/problem/65/) ```cpp= #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; signed main(){ int n,m; cin>>n>>m; int arr[n]; for(int i=0;i<n;i++) cin>>arr[i]; while(m--){ int x; cin>>x; cout<<lower_bound(arr,arr+n,x)-arr+1<<'\n'; } return 0; } ``` ---- 不要太常用lower_bound()和upper_bound()，因為很多題目還是需要自己定義二分搜的判別條件，像是前面的 Example 2~5 ，而且APCS觀念題幾乎每次都會考一兩題二分搜，所以還是好好練習手刻吧XD ---- 練習題(們)： [binary search](https://csdc.tw/problems/?tag=binary%20search) --- ## Thank you for listening!