二分+例题

二分主要是在有序的数组或着类似有序性质的数组里查找元素，时间复杂度是O(logn)

题目链接：查找（二分模板）

/*时间复杂度为O(m logn)*/
#include<bits/stdc++.h>
using namespace std;
int n,p;
long long q,a[1000005];int find(int x){int l=1,r=n;while(l<r){//注意不要写 l<=r ,否则TLE int mid=(l+r)>>1;if(a[mid]<x) l=mid+1;else r=mid;}if(a[l]==x) return l;else return -1;
}int main(){cin>>n>>q;for(int i=1;i<=n;i++) cin>>a[i];while(q--){int x;cin>>x;cout<<find(x)<<" ";}
}

使用STL 自带的二分函数—— upper_bound 和 lower_bound：

函数的用法：lower_bound(a.begin(),a.end(),x) 返回第一个大于等于 x的数的地址。而由于是地址，在最后要 −a（也就是减去地址），upper_bound(a.begin(),a.end(),x)返回第一个大于 x的数的地址

二分函数详细解释

//
#include<bits/stdc++.h>
using namespace std;
int n,p;
long long q,a[1000005];int main(){cin>>n>>q;for(int i=1;i<=n;i++) cin>>a[i];while(q--){int x;cin>>x;int p=lower_bound(a+1,a+n+1,x)-a;//注意数组是从下标为1的位置开始存数的，不要忘记+1 if(a[p]==x) cout<<p<<" ";else cout<<-1<<" ";}
}