二分爆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 + (r - l) / 2

这个表达式转换一下:$l + \frac{r - l}{2}$, 也就是$\frac{2 \times l + 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了。

附:整型浮点型爆炸极限

类型名二分爆炸极限EPS建议值
intl = 0, r = 1073741823???
long longl = 0, r = 4.6e18???
double???1e-8(可存15位十进制)
long double???1e-26(可存33位十进制)
Licensed under CC BY-NC-SA 4.0