二分爆long long解决方法

看二分代码总有一行不理解

爆掉出现的问题

此处使用爆int举例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>

using namespace std;

bool check(int x) {
    return x > 1919810;
}

int main() {
    int l = 114514, r = 2.14748e9;
    while ((r - l) > 1) {
        // 1.
        int mid = (l + r) / 2;
        // 2.
        int mid = l + (r - l) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    cout << l << endl;
    return 0;
}

结果是:

使用1号代码输出-1073686390,使用2号代码输出1919810

为什么它等于mid

$L+\frac{R-L}{2} = \frac{2L + R - L}{2} = \frac{L + R}{2}$

就是lr的平均值mid

为什么不会爆

首先,一般的二分答案都是二分正数(不是的话,答案范围一般不大,如浮点二分三次方根),那r - l就不会爆。

r - l不爆,(r - l) / 2也不会爆。

至于l + (r - l) / 2,很明显,这个值一定在lr之间,既然lr不爆,那这个就不可能爆。

总结

当然,除非真的要爆long long了才会用这招,不然写错了可就爆0了。

注:写二分也要注意边界条件哈,听说只有 $10%$ 的程序员能写对二分hhh。

附:整型浮点型爆炸极限

类型名二分爆炸极限EPS建议值
int$l = 0, r = 10^{9}$???
long long$l = 0, r = 4.6 \times 10^{18}$???
double???$10^{-8}$ 一般就用 $10^{-5}$(可存15位十进制)
long double???$10^{-26}$ 一般不用太精确,所以 $10^{-15}$ 就差不多(可存33位十进制)
Built with Hugo
主题 StackJimmy 设计