二分 | 洛灵酱的小窝

洛灵酱的小窝

闻道有先后，术业有专攻。

0%

二分

发表于 更新于 分类于 Valine：

二分查找

mid = (l + r) / 2;等价于mid = l + (r - l) / 2。

第一种写法可能会爆int。

求最小值最大（最大值最小）一般使用二分答案来进行求解。

整数二分

1
2
3
4
5
6
7
8
9
int erfen(int l, int r) {
    int mid;
    while (l <= r) { // 注意二分条件
        mid = (l+r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

实数二分

1
2
3
4
5
6
7
8
9
double erfen(double l, double r) { // dlt = 0.001(精度)
    double mid;
    while (fabs(l-r) > dlt) {
        mid = (l+r) / 2.0;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}