[C++知识库]二分查找方法边界选取问题

这两天刷题时做二分法的题十分纠结，在寻求边界的时候，总是因为不同的题目而被绕进去，看了一个评论总结的方法，思路清晰了很多。

现定义变量

\\l为左边界
\\r为右边界
\\mid为中点

在二分法中，不同的题解变量的表达方式不唯一，这样非常容易混淆不同变量的值。实际上只看左边界，即可将所有问题归纳在一起。左边界有两种取法，一种为 l = mid，另一种为 l = mid + 1。

\\ 类型一
int bisection(int l, int r){
    while(l<r){
        int mid = (l + r)<<1;
        if(check(mid)) r = mid;
        else{
        l = mid+1;      
        }
}
    return l;
}


\\ 类型二
int bisection(int l,int r){
        while(l<r){
        mid = (l+r+1)<<1;
        if(check(mid)){
        l = mid;
    }else{
        r = mid - 1;
}
}
    return l;



}

对于类型1，l=1，r=2， mid=(1+2)/2，取整后mid=1，l=1+1=2，变量成功更新， 没有进入死循环。

对于类型2，当l=1，r=2时，如果mid=（1+2）/2，取整后mid=1，这个时候l=mid，相当于左边界没有变换，循环为死循环。故，mid=(r+l+1)>>1。

而如何选择模板，应该根据题目的需求判断左边界的选择，是为mid还是为mid+1，从而选择相应的类型求解。

对于while中的判断，l<r和l<=r均可，如果初始值l有可能等于r时，要使用l<=r，同时代码需要微调

int bisection(int l,int r){
        while(l<=r){
        mid = (l+r)<<1;
        if(check(mid)){
        r = mid - 1;
    }else{
        l = mid + 1;
}
}
    return l;



}