为什么此二进制搜索实现导致溢出

问题描述 投票:0回答:2

在执行二进制搜索时

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;

我不知道为什么更新后的语句没有溢出问题。根据我的理解,迟早,更新的语句也会出现溢出问题。

谢谢

algorithm
2个回答
4
投票

[原始对象可能溢出,因为l+u可能大于int可以处理的最大值(例如,如果lu都为INT_MAX,则它们的总和显然会超过INT_MAX)。

正确的方法不会溢出,因为u-l显然不会溢出,并且l+(u-l)/2被保证为<=u,所以也不会溢出。


0
投票

m = (l+u)/2的初始计算由于添加了非常大的数而导致溢出。因此,这些数字的差异不会导致这种溢出情况,这就是为什么我们使用此公式计算m=l+(u-l)/2。希望你能得到答案

© www.soinside.com 2019 - 2024. All rights reserved.