java - 中点公式溢出错误

Question

我正在学习算法/big o，我只是对此感到好奇。

使用

 mid = (low+high)/2;

为了获得中点，通常不鼓励使用二分查找算法，因为可能会出现溢出错误。为什么会出现溢出错误，怎么办

 mid = low + (high-low)/2;

防止这个错误？

谢谢。

Answer 1

在第一种情况下，如果 low 和 high 都足够大(比如两者都等于 2^30+1/或什至更大/)。在第二种情况下，你不计算 (low+high)，你做了一个小技巧，然后遍历表达式 (high-low) 并且该表达式相对于 int 溢出要安全得多。

不过，如果你没有一个大小大于 2^30 的数组(无论如何这是一个相当大的数组)，即使使用第一个表达式，我也看不出你怎么会遇到 int 溢出.所以在大多数情况下我只会使用第一个而不用担心。