lower

lower_bound（first,last,val）表示找到第一个>=val的值的地址 upper_bound（first,last,val）表示找到第一个>val的值的地址

在lower_bound（first,last,val，cmp）中cmp是比较函数

在lower_bound（first,last,val）中cmp默认为

bool cmp（mid，val）｛ return mid<val;//表示如果mid<val 则继续lower_bound ｝

所以当mid>=val时停止 时间复杂度O（logn） 附上测试代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<ctime> #include<cstdlib> #define N 110 #define MOD 100 using namespace std; int a[N],b[N],n; bool cmp(int p,int q){ return p<q; } int main(){ srand((unsigned)time(NULL)); n=rand(); for(int i=1;i<=n;i++)a[i]=rand()%MOD; for(int i=1;i<=n;i++)b[i]=rand()%MOD; sort(a+1,a+n+1); for(int i=1;i<=n;i++)printf("%d ",a[i]); printf("\n"); for(int i=1;i<=n;i++)printf("%d ",b[i]); printf("\n"); for(int i=1;i<=n;i++){ printf("%d ",a[lower_bound(a+1,a+n+1,b[i],cmp)-a]); } }

但是

lower_bound的时间常数比较大 （不会lower_bound或p党）可以手写二分查找来替代 如下：（实验证明是有效果的）

inline int Find(int l,int r,int v){ int mid; while(l<r){ mid=(l+r)>>1; if(c[mid]>=v)r=mid; else l=mid+1; } if(c[l]<v)return l+1; return l; }