二分问题

二分问题分为整数二分和浮点二分。

整数二分

二分的本质是边界。假设在一个区间上定义了某种性质，整个区间可以被一分为二，使得这个性质在右半段区间满足而在左半段不满足。二分可以寻找边界，既可以找到左半段的右边界a，也可以找到右半段的左边界b

  l       ab                  r
  xxxxxxxxxoooooooooooooooooooo

对于求两个边界，使用略微不同的模板。

情况一：在右半段寻找左边界（即寻找符合性质的第一个点）

每次将区间划分为[l, mid]和[mid + 1, r]（[l, mid]是因为mid点可能就是左边界，所以这里不用[l, mid - 1]（妙啊））

int bsearch(int l, int r)
{
    while(l < r){
        int mid = (l + r) / 2;
        if(check(mid)) r = mid; //如果符合性质
        else l = mid + 1;
    }
    return l;
}

p.s.这里while(l < r)也很妙，循环停止时肯定有l = r = mid。自己之前一直用l <= r，导致循环停止的时候总得看l和r是相等还是某个超出去1.

情况二：在左半段寻找右边界（即寻找不符合性质的最后一个点）

每次将区间划分为[l, mid - 1]和[mid, r]（这是因为如果mid点符合性质，那么下次划分右边界肯定从mid-1开始）

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

p.s.mid = (l + r + 1) / 2这里，+1是因为除法下取整，在r = l + 1时更新l = mid时会出现l = mid = l的死循环。+1则相当于上取整，解决了这个隐患。

浮点二分

通常是函数求根、开方等问题，比较简单，while循环终止条件是精度e，更新时l和r都更新为mid即可。

例题 https://www.acwing.com/activity/content/problem/content/824/1/ 求数的三次根号

方法一：pow函数。注意pow(x, y)中x不能是负数，需特殊处理

if(n >= 0) res = pow(n, 1.0 / 3);
else res = (-1) * pow((-1)*n, 1.0 / 3);

方法二：cbrt函数(STL)

res = cbrt(n);

方法三：浮点二分

int main()
{
    double n;
    cin >> n;
    double l = -10000, r = 10000, mid; //注意范围，有的数开方后比原数大
    while(r - l > 1e-7){
        mid = (l + r) / 2;
        if(mid * mid * mid >= n) r = mid;
        else l = mid ;
    }
    printf("%.6f", l);
}