爆掉出现的问题
此处使用爆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位十进制) |