二分查找

代码模板

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