UPD: 2025-07-15
爆掉出现的问题
此处使用爆int举例:
|
|
结果是:
使用1号代码输出-1073686390,使用2号代码输出1919810。
为什么它等于mid
$L+\frac{R-L}{2} = \frac{2L + R - L}{2} = \frac{L + R}{2}$
就是l和r的平均值mid。
为什么不会爆
首先,一般的二分答案都是二分正数(不是的话,答案范围一般不大,如浮点二分三次方根),那r - l就不会爆。
r - l不爆,(r - l) / 2也不会爆。
至于l + (r - l) / 2,很明显,这个值一定在l和r之间,既然l和r不爆,那这个就不可能爆。
总结
当然,除非真的要爆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位十进制) |