algorithm - 为什么这个二进制搜索实现会导致溢出？

Question

二分查找中的实现

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;

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

Answer 1

原件可能溢出，因为l+u可能大于最大值 int可以处理(例如，如果 l 和 u 都是 INT_MAX 那么它们的总和显然会超过 INT_MAX )。

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