二分的正确姿势

简单问题不能出错

//>=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;
        }

标签: 算法, 学习

添加新评论