algorithm - 在二进制搜索中计算中间值

Question

我正在阅读一本算法书，其中包含以下二进制搜索算法:

public class BinSearch {
  static int search ( int [ ] A, int K ) {
    int l = 0 ;
    int u = A. length −1;
    int m;
    while (l <= u ) {
      m = (l+u) /2;
      if (A[m] < K) {
        l = m + 1 ;
      } else if (A[m] == K) {
        return m;
        } else {
          u = m−1;
        }
       }
       return −1;
      }
 }

作者说“错误在赋值 m = (l+u)/2; 中，它会导致溢出，应该替换为 m = l + (u-l)/2。”

我看不出这会导致溢出。当我在脑海中针对几个不同的输入运行算法时，我没有看到 mid 的值超出数组索引。

那么，在哪些情况下会发生溢出呢？

Answer 1

这post详细介绍了这个著名的错误。正如其他人所说，这是一个溢出问题。链接上推荐的修复方法如下:

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

// Alternatively
int mid = (low + high) >>> 1;

可能还值得一提的是，如果允许使用负索引，或者它甚至不是正在搜索的数组(例如，在满足某些条件的某个整数范围内搜索一个值)，则上面的代码可能不是也正确。在这种情况下，像

这样丑陋的东西

(low < 0 && high > 0) ? (low + high) / 2 : low + (high - low) / 2

可能是必要的。一个很好的例子是 searching for the median in an unsorted array without modifying it or using additional space通过简单地对整个 Integer.MIN_VALUE–Integer.MAX_VALUE 范围执行二进制搜索。