为什么这种二分查找实现会导致溢出？
在二分查找的实现中
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;
不知道为什么更新后的语句没有溢出问题。根据我的理解， 迟早，更新后的语句也会出现溢出问题。
In the implementation of binary search
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
...
}
}
The correct method is as follows:
m = l + (u -l )/2;
I don't know why the updated statement has no overflow issue. Based on my understanding,
soon or later, the updated statement will also have overflow issue.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
原始数据可能会溢出，因为
l+u可能大于int可以处理的最大值（例如，如果l和u是INT_MAX那么它们的总和显然会超过INT_MAX）。正确的方法是不会溢出的，因为
ul显然不会溢出，而且l+(ul)/2保证为<=u，所以也不能溢出。The orignal may have overflow because
l+ucould be greater than the maximum value anintcan handle (e.g. if bothlanduwereINT_MAXthen their sum would obviously exceedINT_MAX).The correct method can't overflow, because
u-lobviously won't overflow, andl+(u-l)/2is guaranteed to be<=u, so can't overflow either.由于添加了非常大的数字，
m = (l+u)/2的初始计算会产生溢出。因此，这些数字的差异不会导致这种溢出情况，这就是我们使用此公式计算
m=l+(ul)/2的原因。The initial Calculation of
m = (l+u)/2create overflow due to addition of very large numbers.So, Difference of these numbers does not cause this overflow condition ,that's why we are calculating
m=l+(u-l)/2using this formula.