二分的正确姿势
简单问题不能出错
//>=x的第一个
int find(int l,int r,int x){
while(l<r){
int mid=l+r>>1;
if(a[mid]>=x) r=mid;
else l=mid+1;//a[mid]<x mid必然不可能
}
return a[l];
}
//<=x的最后一个
int find(int l,int r,int x){
while(l<r){
int mid=l+r+1>>1; //r-l==1时,若mid=l+r>>1,则mid=l,if进入死循环,else进入r=l-1
if(a[mid]<=x) l=mid;
else r=mid-1;//a[mid]>x mid必然不可能
}
return a[l];
}
int l=0,r=n,mid,ans=0;
while(l<=r){
mid=(l+r)>>1;
if(check(mid)) l=mid+1,ans=mid;
else r=mid-1;
}