在执行二进制搜索时
int search(int[] A, int K) {
int l = 0;
int u = A.length - 1;
int m
while ( l <= u ) {
m = (l+u)/2; // why this can cause overflow
...
}
}
正确的方法如下:
m = l + (u -l )/2;
我不知道为什么更新后的语句没有溢出问题。根据我的理解,迟早,更新的语句也会出现溢出问题。
谢谢
[原始对象可能溢出,因为l+u
可能大于int
可以处理的最大值(例如,如果l
和u
都为INT_MAX
,则它们的总和显然会超过INT_MAX
)。
正确的方法不会溢出,因为u-l
显然不会溢出,并且l+(u-l)/2
被保证为<=u
,所以也不会溢出。
m = (l+u)/2
的初始计算由于添加了非常大的数而导致溢出。因此,这些数字的差异不会导致这种溢出情况,这就是为什么我们使用此公式计算m=l+(u-l)/2
。希望你能得到答案