二分总结

二分模板 (y总算法基础课)

整数二分

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
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;
}

浮点二分

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2; //注意这里只能写 /2 ，不能  >> 1
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

二分规律

本质规律

• 是否能进行二分？即答案是否具有二段性或单调性
• 怎么进行二分？即check()函数怎么写
• check()函数怎么写是最重要的，题目所问的其实很有可能就是最终二分的目标对象，这个时候去看一下有没有可能在目标对象上面存在线性的关系，如果有可能就可以考虑用二分，因此可以从此观察check()与线性关系

例题

大多数情况下，二分都和其他算法相结合，二分算法只是起到辅助降低复杂度的作用

1. 机器人跳跃问题

Acwing 730

二分 + 递推

• 递推: 从题意来看，可以递推出当前的能量公式：$ E′=2E−H(k+1)$
• 二分： 能量公式表明，能量值是线性的，因此$E$是否$>0$就是$check()$条件

2. 四平方和

Acwing.1221

标签是二分，实则是暴力

• 暴力 + 二分查找/哈希表即可

3. 分巧克力

Acwing.1229

题意为在限制条件下找出最大的边长，我觉得这是一个非常明显的二分

• 对谁二分？ 很明显我们需要二分的是巧克力的长度
• check()怎么写？对于每一种边长，需要满足的条件是至少分出$K$块巧克力

4.