搜尋、二分搜尋、跳躍二分搜
前提
distance(it_a , it_b);
計算兩個迭代器之間的距離
distance(v.begin(),find(v.begin(),v.end(),5))
會回傳找到的位置
搜尋
使用於未排序之資料
函數的find為O(n)
(若在已經排序(set、map)的find為O(log n)
#include<bits/stdc++.h>
using namespace std;
#define nn "\n";
int main(){
vector<int>v;
v.push_back(2);
v.push_back(3);
v.push_back(1);
v.push_back(5);
v.push_back(6);
for(int i:v){
cout<<i<<" ";
}cout<<nn;
cout<<"5的位置： "<< distance(v.begin(),find(v.begin(),v.end(),5));
}
2 3 1 5 6
5的位置： 3
二分搜尋(自製)
只可用於已排序之資料
例如：set、map、multiset、multiset、已排序陣列
二分搜尋有兩種情況：
1.要找的值在陣列中
2.要找的值不在陣列中
以下分別說明
要找的值在陣列中
如果要找的值在集合中，就會回傳index，否則回傳-1
#include<bits/stdc++.h>
using namespace std;
int by(vector<int>v,int L,int R,double x){
while(L<=R){
int mid=(L+R)/2;
if(v[mid]==x){
return mid;
}
else if(x<v[mid]){
R=mid-1;
}
else{
L=mid+1;
}
}
return -1;
}
int main(){
vector<int>v={11,12,13,14,15,16,17,18,19};
int n=v.size();
cout<<by(v,0,n,15);
}
要找的值不在陣列中
如果要找的值不在陣列中，我們或許會想要找到「所有大於x的值」，或是「所有小於x的值」。
透過以下程式碼，可以看到，如果沒有在陣列中找到對應的數值(x)：
- L為：「小於x且最接近x的數」的index+1
- R為：「大於x且最接近x的數」的index-1
#include<bits/stdc++.h>
using namespace std;
void by(vector<int>v,int L,int R,double x){
while(L<=R){
int mid=(L+R)/2;
if(v[mid]==x){
cout<<mid;
return;
}
else if(x<v[mid]){
R=mid-1;
}
else{
L=mid+1;
}
}
cout<<L<<" "<<R<<"\n";
return ;
}
int main(){
vector<int>v={11,12,13,14,15,16,17,18,19};
int n=v.size();
by(v,0,n,10); //0 -1
by(v,0,n,16.5); //5 4
by(v,0,n,20); //10 9
}
這樣我們如果要找到所有小於等於x的數，可以執行以下程式。
#include<bits/stdc++.h>
using namespace std;
int by(vector<int>v,int L,int R,double x){
while(L<=R){
int mid=(L+R)/2;
if(v[mid]==x){
return mid+1; //注意這邊要加一！！！
}
else if(x<v[mid]){
R=mid-1;
}
else{
L=mid+1;
}
}
return L;
}
int main(){
vector<int>v={11,12,13,14,15,16,17,18,19};
int n=v.size();
cout<<by(v,0,n,14.5)<<" ";
cout<<by(v,0,n,15);
}
內建二分搜
種類有:
1. find
直接回傳位置
2. lower_bound
回傳大於等於n的「最小值」
3. upper_bound
回傳大於n的「最小值」網站資料：
https://blog.csdn.net/tjpuacm/article/details/26389441
find
- 若資料結構為陣列，直接使用lower_bound，然後因為lower_bound包含=，再排除大於的即可。
- set、map：
#include<bits/stdc++.h> using namespace std; #define nn "\n"; int main(){ set<int>s; s.insert(1); s.insert(5); s.insert(6); s.insert(7); s.insert(4); if(s.find(5)!=s.end()){ cout<<"found"; } else{ cout<<"Not found"; } cout<<nn; if(s.find(2)!=s.end()){ cout<<"found"; } else{ cout<<"Not found"; } }
lower_bound、upper_bound：O(log n)
lower的意義是對於給定的已經排好序的a，
key最早能插入到那個位置 0 1 | 2 2 3 所以2最早插入到2號位置。upper的意義是對於給定的已經排好序的a，
key最晚能插入到那個位置 0 1 2 2 | 3 所以2最晚插入到4號位置。
#include<bits/stdc++.h>
using namespace std;
#define nn "\n";
int main(){
vector <int> v={1,2,5,4,7,8,9};
sort(v.begin(),v.end());
cout<<*lower_bound(v.begin(),v.end(),7);
cout<<nn;
cout<<*upper_bound(v.begin(),v.end(),7);
}
7
8
#include<bits/stdc++.h>
using namespace std;
#define nn "\n";
int main(){
set<int>s;
s.insert(1);
s.insert(5);
s.insert(6);
s.insert(7);
s.insert(4);
cout<<*s.lower_bound(4);
cout<<nn;
cout<<*s.upper_bound(4);
}
4
5
自定義lower_bound、upper_bound
當陣列中是一個pair或是tuple時要告訴程式該依照哪一個元素來找
#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<int, int> a, pair<int, int> b) {
return a.second < b.second; //lower_bound和upper_bound都只能用"<"
}
int main() {
vector<pair<int, int>> v;
v.push_back({1, 2});
v.push_back({2, 4});
v.push_back({3, 6});
v.push_back({4, 8});
pair<int, int> pa = {0, 6};//只比較後面，所以前面是0沒差，然後要用pair或是要自己定義operator<
cout << (*lower_bound(v.begin(), v.end(), pa, cmp)).second << "\n";
cout << (*upper_bound(v.begin(), v.end(), pa, cmp)).second;
}
P-2-6. Two-Number problem
題目：https://judge.tcirc.tw/ShowProblem?problemid=d015
假設 A 為 m 個相異整數的集合，B 為 n 個相異整數的集合，而 K 是一個整數。請計算有多少對(a, b)的組合滿足 a 屬於 A, b 屬於 B 且 a+b = K。
Time limit: 1 秒
輸入格式：輸入可能有多行，第一行有三個整數 m, n 與 K，第二行有 m 個整數是 A
中的元素，第三行有 n 個整數 B 中的元素一筆測資。同一行相鄰數字間以空白間隔。
兩集合元素個數均不超過 10 萬，整數的絕對值不超過 10 億。
輸出格式：輸出組合個數。
範例輸入：
3 4 2
1 6 -3
5 1 -1 -3
範例輸出：
2
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0),cin.tie(0);
int m,n,k;
cin>>m>>n>>k;
//a放陣列
int v[m];
for(int i=0;i<m;i++){
cin>>v[i];
}
//b放set(要排序)
set<int>s;
for(int i=0;i<n;i++){
int x;
cin>>x;
s.insert(x);
}
//由a搜b中是否有k-a
int ans=0;
for(int i=0;i<m;i++){
if(s.find(k-v[i])!=s.end()){
ans++;
}
}
cout<<ans;
}
跳躍二分搜
Danger | 注意！！！
裡面是while不是if
這是比較特別的二分搜尋，用來解決一個數列可以分兩半，找到前半邊的最後一項(例如：大於目標數值、小於目標數值)他的對象也是已排序的陣列，以二分搜找出小於或是小於等於目標數值的index
我們來看看它的運作過程：
他先把跳躍的距離(junp)設為總大小的一半
接著確認跳了之後的 v[junp] 是否小於目標
如果小於：代表可以跳(將index加上junp)
如果不會：那就把跳躍的距離除以二直到可以跳，或是jump=0，如果等於零
就代表已經找到了小於目標數值的最大值
跳了第一次之後就會遇到問題：有可能會超出陣列範圍，導致無法找到v[index]，所以判斷可以跳的條件為：
1. 跳了不會超出陣列範圍
2. 跳了之後能夠小於目標數值
全部可分為兩半：小於6、大於6
我們來看找尋小於物標數值(6)的最大值例子：int v[10]={1,3,4,5,7,9,11,14,15,19}; //遞增陣列 int L=0,R=10; //起點、終點 int x=6 //目標數值 int index; //位置
#include<bits/stdc++.h>
using namespace std;
#define nn "\n"
int main(){
int v[10]={1,3,4,5,7,9,11,14,15,19};
int L=0,R=10;
int x=6;
int index=L;
for (int jump = (R-L)/2; jump>0;jump>>=1) {
while (index+jump<R && v[index+jump]<x){
index += jump;
}
}
cout<<index;
}
3
判斷「是否有找到」
#include <bits/stdc++.h>
using namespace std;
#define nn "\n"
#define int long long
int v[1000]; // index
int n;
int jumpfind(int x) { // find_the_last(<=x)
int i = 0;
for (int j = n / 2; j > 0; j >>= 1) {
while ((i + j <n) && (v[i + j] <= x )) {
i += j;
}
}
// 檢查是否找到符合條件的元素
if (v[i] <= x) {
return i;
} else {
return n; // 沒找到，返回n
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
istringstream cin("6 \
1 2 5 7 8 9");
cin>>n;
for (int i = 0; i < 6; i++) {
cin >> v[i];
}
int x = 8;
cout << "x: " << jumpfind(x) << nn;
return 0;
}
前面提到可分為兩半，小於6、大於6
在第11行的while (index+jump<R && v[index+jump]<x){中，v[index+jump]<x就是用來分辨是否小於6要如何思考寫大於6還是小於6呢？
起點位置小於6，所以就是小於6跳躍二分搜適合用於有單調性的題目喔
在貪心演算法有一題「P-4-9. 基地台 (APCS201703) 」可以練習看看