C++二分查找

 

代码模板

int bsl(int l, int r) //返回左边界
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) //每次正确右边界都向左缩小
            r = mid;
        else
            l = mid + 1; //mid不正确,弃用mid并且缩小区间
    }
    return l;
}

int bsr(int l, int r) //返回右边界
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) //每次左边界都向右缩小,由于存在向下取整,避免死循环mid需要l+r+1
            l = mid;
        else
            r = mid - 1; //mid不正确,弃用mid并缩小区间
    }
}

代码原理

bsl为例

​ 二分的主要的作用,是取得一个“分界点”。采取的思路为测试中间点是否符合条件,如果不符合则对区间进行缩小操作,重新测试区间,直到区间为一个数字。在模板一中,首先确定中间点mid,然后测试中间点mid是否符合条件,如果符合条件,则每次都会将区间的右端点进行左移的操作,直到不能左移为止,所以返回的最后位置为最接近答案的最左边的端点。如果不符合条件,由于确定了mid 的位置为无效位置,所以下一次刷新区间的时候将mid剔除掉。剔除的操作可以达到防止死循环的效果

时间复杂度

​ 由于二分是每次都将一个区间一分为二,并且对整个区间进行一次操作,所以最后的时间复杂度为O(logN)

需要注意的点

  1. bsr中,由于在每次正确的时候修改的都是左边界l,但是在计算除2的时候会存在mid/2取整为l的情况,这样会导致最后结果的死循环。所以需要定义mid为mid = l+r+1>>1来避免死循环。可以记为 返回右边界的时候需要+1,因为右边比左边大(bushi