在二进制搜索中计算mid

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

这篇文章详细介绍了这个着名的bug.正如其他人所说,这是一个溢出问题.链接上建议的修复方法如下:

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范围.

Answer 2

以下 C++ 程序可以向您展示 32 位无符号整数如何发生溢出：

#include <iostream>
using namespace std;

int main ()
{
  unsigned int  low = 33,  
                high = 4294967290, 
                mid;

  cout << "The value of low is " << low << endl;
  cout << "The value of high is " << high << endl;

  mid = (low + high) / 2;

  cout << "The value of mid is " << mid << endl;
  
  return 0;
}

如果你在 Mac 上运行它：

$ g++ try.cpp; ./a.out
The value of low is 33
The value of high is 4294967290
The value of mid is 13

的值mid可能是2147483661，但low + high由于 32 位无符号整数不能包含正确的值而溢出27，因此返回，因此mid变为13。

当计算mid改变为

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

然后它会显示

The value of mid is 2147483661

简单的答案是，添加l + u可能会溢出，并且在某些语言中具有未定义的行为，如Joshua Bloch 的博客文章中所述，关于 Java 库中用于实现二进制搜索的错误。

有些读者可能不明白它是关于什么的：

l + (u - l) / 2

注意，在某些代码中，变量名不同，是

low + (high - low) / 2

答案是：假设您有两个数字：200 和 210，现在您想要“中间数字”。假设您将任意两个数字相加并且结果大于 255，那么它可能会溢出并且行为未定义，那么您能做什么？一个简单的方法是将它们之间的差值，但只是其中的一半，添加到较小的值上：看看 200 和 210 之间的差值是多少。它是 10。（您可以将其视为“差异”或“长度” “， 它们之间）。所以你只需要加到10 / 2 = 5200，然后得到 205。你不需要先把 200 和 210 加在一起——这就是我们如何计算的：(u - l)区别。(u - l) / 2是一半。将其添加到l我们有l + (u - l) / 2.

就像，如果我们在看两棵树，一棵高 200 英尺，一棵高 210 英尺，“中点”或“平均值”是什么？我们不必先将它们加在一起。我们可以分辨出差异是 10 英尺，我们可以将其中的一半（5 英尺）加到 200 上，我们知道它是 205 英尺。

从历史的角度来看，Robert Sedgewick 提到第一次二分查找是在 1946 年提出的，直到 1964 年才正确。 Jon Bentley 在 1988 年的《Programming Pearls》一书中描述，超过 90% 的专业程序员不能在几个小时内正确地写出来。但即使是 Jon Bentley 本人也有 20 年的溢出漏洞。1988 年发表的一项研究表明，在 20 部教科书中，只有 5 部能找到准确的二分查找代码。2006 年，Joshua Bloch 写了一篇关于计算mid值的错误的博客文章。所以这段代码花了 60 年才正确。但是现在，下次在求职面试中，请记住在 5 分钟内正确地写出来。

Answer 3

问题是(l+u)首先被评估，并且可能会溢出int，因此(l+u)/2将返回错误的值。

Answer 4

杰夫建议阅读有关此错误的非常好的帖子，如果您想快速概览，这里是摘要。

在 Programming Pearls Bentley 说类似的行“将 m 设置为 l 和 u 的平均值，并截断为最接近的整数。” 从表面上看，这个断言可能看起来是正确的，但是对于 int 变量 low 和 high 的大值来说它失败了。具体来说，如果 low 和 high 的总和大于最大正整数值 (2^31 - 1)，则失败。总和溢出为负值，除以 2 时该值保持为负。在 C 中，这会导致数组索引超出范围并产生不可预测的结果。在 Java 中，它会抛出 ArrayIndexOutOfBoundsException。

Answer 5

这是一个示例，假设您有一个非常大的数组，其大小2,000,000,000为10 (10^9 + 10)，左侧index为2,000,000,000，右侧index为2,000,000,000 + 1。

通过使用lo + hi将求和2,000,000,000 + 2,000,000,001 = 4,000,000,001。由于 an 的最大值integer为2,147,483,647. 所以你不会得到4,000,000,000 + 1，你会得到一个integer overflow。

但low + ((high - low) / 2)会起作用。2,000,000,000 + ((2,000,000,001 - 2,000,000,000) / 2) = 2,000,000,000