codeforces上的代碼是開放的，常常就能看到本渣與大神們的差距

比如二分查找。。。

1.在數組中，找出第一個4所在位置

輸入：

14 4 1 2 2 3 4 4 4 4 5 6 7 9 9 10

這是本鶸代碼。。。。。。。

#include <stdio.h> int a[1010],n; int main(){int i,l,r,mid,b;scanf("%d%d",&n,&b);for(i=1;i<=n;i++)scanf("%d",&a[i]);l=0,r=n;while(l+1<r){mid=(l+r)/2;if(a[mid]<b)l=mid;else r=mid;//a[mid]>=b}if(a[r]==b)printf("%d\n",r);//找數字b出現在最左側else printf("NO\n");return 0; }

輸出：

５

然而大神是這樣寫的：

#include <cstdio> #include <algorithm> using namespace std; int a[1010],n; int main(){int i,b,pos;scanf("%d%d",&n,&b);for(i=1;i<=n;i++)scanf("%d",&a[i]);pos=lower_bound(a+1,a+1+n,b)-a;//找數字b出現在最左側if(pos==n+1||a[pos]!=b)printf("NO\n");else printf("%d\n",pos);//a[pos]==b;return 0; }

2.在數組中，找出最后一個4所在位置

輸入：

14 4 1 2 2 3 4 4 4 4 5 6 7 9 9 10

這是本鶸代碼。。。。。。。

#include <stdio.h> int a[1010],n; int main(){int i,l,r,mid,b;scanf("%d%d",&n,&b);for(i=1;i<=n;i++)scanf("%d",&a[i]);l=1,r=n+1;while(l+1<r){mid=(l+r)/2;if(a[mid]<=b)l=mid;else r=mid;}if(a[l]==b)printf("%d\n",l);//找數字b出現在最右側else printf("NO\n");return 0; }

然而大神是這樣寫的：

#include <cstdio> #include <algorithm> using namespace std; int a[1010],n; int main(){int i,b,pos;scanf("%d%d",&n,&b);for(i=1;i<=n;i++)scanf("%d",&a[i]);pos=upper_bound(a+1,a+1+n,b)-a;//找數字b出現在最右側if(pos==n+1||a[pos-1]!=b)printf("NO\n");else printf("%d\n",pos-1);//a[pos-1]==b;return 0; }

3.用法

頭文件：#include <algorithm>

時間復雜度：一次查詢O(log n)，n為數組長度。

圖示：

lower_bound：

功能：查找非遞減序列[first,last) 內第一個大于或等于某個元素的位置。

返回值：如果找到,則返回找到元素的地址;否則返回last的地址。（這樣不注意的話會越界，小心）

用法：int t=lower_bound(a+l,a+r,key)-a；(a是數組)。

upper_bound:

功能：查找非遞減序列[first,last) 內第一個大于某個元素的位置。

返回值：如果找到,則返回找到元素的地址;否則返回last的地址。（同樣這樣不注意的話會越界，小心）

用法：int t=upper_bound(a+l,a+r,key)-a；(a是數組)。

摘自https://blog.csdn.net/lwgkzl/article/details/82851346

結構體中查找：

把我們需要查找的數封裝成一個結構體。然后才可以在結構體重進行查找。即使我們只需要針對某一維進行查找，也需要把整個結構體構造出來。

代碼如下：

struct MY{int a,b;MY(){}MY(int a,int b):a(a),b(b){}bool operator<(const MY m)const{ //定義比較方式，這一步很重要return a<m.a;} };int main(){MY m[10];for(int i=0;i<10;i++){m[i] = MY(i+1,2*i);cout<<m[i].a<<" "<<m[i].b<<endl;}cout<<"請輸入你需要查找的數字a:"<<endl;int num;cin>>num;sort(m,m+10);//進行二分之前需要排序int aa = lower_bound(m,m+10,MY(num,0)) - m; //需要把我們查找的數封裝成一個結構體才能進行查找。cout<<"查到位置為："<<aa<<endl;return 0; }

這里我只需要查找第一維，并且我對第一維進行了排序，只有有序數列才可以進行二分，然后在查找的時候，把其他維置零即可。但是必須要封裝成一個結構體

vector中也是同理：

代碼：

struct MY{int a,b;MY(){}MY(int a,int b):a(a),b(b){}bool operator<(const MY m)const{ //定義比較方式，這一步很重要return a<m.a;} };int main(){vector<MY>ve;for(int i=0;i<10;i++){ve.push_back(MY(i+1,2*i));cout<<ve[i].a<<" "<<ve[i].b<<endl;}cout<<"請輸入你需要查找的數字a:"<<endl;int num;cin>>num;sort(ve.begin(),ve.end());//進行二分之前需要排序int aa = lower_bound(ve.begin(),ve.end(),MY(num,0)) - ve.begin(); //需要把我們查找的數封裝成一個結構體才能進行查找。cout<<"查到位置為："<<aa<<endl;return 0; }

ve.begin()指向vector的開始，ve.end()指向vector的結尾。

結果如下：

?摘自https://blog.csdn.net/codehappy123/article/details/97814162

輸入N個字符串后，排個序，同時記錄他在未排序之前的編號。所以這需要結構體。然后就是對結構體排序。之后需要在最快時間內找到前綴為s的第一個字符串，需要使用二分中 的lower_bound（） 所以我們需要運用重載運算符，重新定義查找規則。

值得注意的是lower_bound（）中第三個參數也必須是一個結構體，所以你需要將前綴字符串s封裝成結構體才可以查詢。
?

#include <bits/stdc++.h> using namespace std; struct node {int i;string s;bool operator<(const node m)const{return s<m.s;} }hah[1000006]; char ch[1000006]; bool cmp(struct node x,struct node y) {return x.s<y.s; } int main() {int n,m;scanf("%d %d",&n,&m);for(int i=0;i<n;i++){scanf("%s",ch);hah[i].s=ch;hah[i].i=i;}sort(hah,hah+n,cmp);while(m--){string c;int k;struct node kk;scanf("%d %s",&k,ch);c=ch;kk.s=c;int tt=lower_bound(hah,hah+n,kk)-hah;if(hah[tt+k-1].s.find(c)!=0)printf("-1\n");else printf("%d\n",hah[tt+k-1].i+1);}return 0; }

?

總結

以上是生活随笔為你收集整理的STL之lower_bound,upper_bound二分查找函数 结构体的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。