计算二进制搜索的中间值

一尘不染

计算二进制搜索的中间值

algorithm

我正在阅读一本算法书，该书具有以下用于二进制搜索的算法：

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。”

我看不到那会导致溢出。当我在脑海中为几个不同的输入运行算法时，看不到中间值从数组索引中消失。

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

阅读 327

2020-07-28

共1个答案

一尘不染

这篇文章详细介绍了这个著名的错误。正如其他人所说，这是一个溢出问题。链接上建议的修复程序如下：

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

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

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

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

可能是必要的。一个很好的例子是在不修改它，或者使用额外的空间搜索中未排序阵列中值通过简单地执行对整个二进制搜索Integer.MIN_VALUE- Integer.MAX_VALUE范围。

2020-07-28