AcWing 789.数的范围
AcWing 790.数的三次方根

二分模板 笔记

二分模板一共有两个，分别适用于不同情况:

$$ 重点 \begin{cases} 主要是 check为 true的部分在前面还是后面 \\ 单调性 \end{cases} $$

• 虽然这模版真的是非常好用，但是每次在决定 check 函数时总是很迷茫，这是我们可以：

假设有一个总区间，经由我们的 check 函数判断后，可分成两部分，
这边以o作 true，.....作 false 示意较好识别

如果我们的目标是下面这个v，那麽就必须使用模板 1
................vooooooooo

假设经由 check 划分后，整个区间的属性与目标v如下，则我们必须使用模板 2
oooooooov...................

所以下次可以观察 check 属性再与模板1 or 2 互相搭配就不会写错啦

也即：模板1就是在满足chek()的区间内找到左边界，模板2在满足check()的区间内找到右边界。
然后无论是左边界还是右边界，都应该是整个区间中某一段满足某性质（如单调不降）
与另一段不满足该性质的分界点（也就是v）

• 算法思路：假设目标值在闭区间[l, r]中， 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

版本1

当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1; 计算mid时不需要加1。

$$ mid = l + r >> 1, if(check(mid)) \begin{cases} true, [l, mid], r = mid \\\\ flase, [mid + 1, r], l = mid + 1 \end{cases} $$

C++ 代码模板：

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

版本2

当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。

$$ mid = l + r + 1 >> 1, if(check(mid)) \begin{cases} true, [mid, r], l = mid \\\\ flase, [l, mid - 1], r = mid - 1 \end{cases} $$

C++ 代码模板：

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