12

二进制搜索可以通过多种方式实现 - 递归、迭代、条件等。我从 Bentley 的书“编程珍珠：编写正确的程序”中获取了这一点，它是一种迭代实现，并且包含一个错误。

 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; 行中发现了一个错误。它可能导致溢出。我们如何避免在这个二分搜索中出现这种溢出？

4

7 回答 7

14

尝试以下操作：

改变

m = (l+u) /2

至

m = (u-l) / 2 + l

(l+u) / 2如果您考虑一个由 2^31 - 1 个元素组成的非常大的数组（有符号的 32 位整数可以容纳的最大值），那么 can 溢出的原因就很明显了。在这种情况下，第一次迭代很好，因为2^31 - 1 + 0没什么大不了的，但考虑一下l = m + 1这里的情况。在第二次迭代中 u 仍然是相同的，而 l 也是2^31 / 2如此l + u将导致溢出。

通过这种方式，我们u + l通过首先确定 l 和 u 之间的相对中间值(u - l) / 2，然后将较小的数字 l 添加到它来避免添加，使其成为绝对值。所以在操作过程中，m = (u-l) / 2 + l;我们永远不会超过 u 的值。

总结完整的代码：

public class BinSearch 
{
    static int search( int [] A, int K ) 
    {
        int l = 0;
        int u = A. length -1;
        int m;

        while ( l <= u ) 
        {
            m = (u-l) / 2 + l;

            if (A[m] < K)
                l = m + 1;
            else if (A[m] == K)
                return m;
            else
                u = m - 1;
        }
        return -1;
     }
}
于 2013-07-07T06:49:07.060 回答
6

假设 l 和 u 都属于 [0, 2^31-1]。如果 l, u >= 2^30，则 (l+u) >= 2^31 溢出。为避免这种情况，请使用

m = l + (u-l)/2;

反而。更重要的是，像这样编写二进制搜索可能更合理：

    public class BinSearch 
    {
        static int search( int [] A, int K ) {
            int l = -1;             // index lower bound shift left by 1
            int u = A.length;       // index upper bound shift right by 1
            int m;
            while ( l + 1 < u ) {
                m = l + (u-l)/2;    // avoid overflow
                if (A[m] < K){
                    l = m;          // keep A[l] < K 
                } else {
                    u = m;          // keep A[u] >= K
                }
            }
            if ( (u == A.length) || (A[u] != K) ) return -1;
            return u;
        }
    }
于 2013-07-08T13:16:33.730 回答
5

正如其他几个人所说，修复很简单，当然是我见过的最简单的 100 点赏金！这是另一个，它具有很好的对称性，即使它需要更多的时钟周期：

m = (l >> 1) + (u >> 1) + (l & u & 1);

在您获得更好的信息之前，您不应该将 Bentley 称为“错误”。当他为 ACM 写那篇文章时（我认为是 1980 年代的某个时候），他正在使用 32 位 C 进行伪编码和编写；不存在具有千兆字节 RAM 的机器。即使他们有 4 字节整数，32 位机器也不能拥有超过 2^28 个整数的数组。因此，可能的最高索引是 2^28-1。将该值加倍不会导致 inint溢出。

当然，32 位 Java 也完全一样。您需要 64 位 Java 的损坏组件 - 一种允许大小接近 2^64 的对象但将索引限制为 2^32-1 以导致此“错误”出现的语言。

你所说的错误是操作假设的改变。如果环境以正确的方式变化，宇宙中的每个程序都会表现出某种缺陷。

于 2013-07-09T21:09:18.793 回答
2

尝试改变

m = (l+u) / 2

至

m = l + (u - l) / 2

看到两者相等并且第二条语句防止溢出是微不足道的。

于 2013-07-07T07:43:02.683 回答
1

迭代实现二分查找确实有bug。改变m = (l+u)/2。正如其他人所提到的，它可能导致整数溢出。将其替换为m = l + (u-l)/2。

根据经验，我一次又一次地看到有缺陷的二进制搜索实现。二进制搜索虽然涉及分而治之的简单概念可能很难正确。m更改上述分配很容易。希望这可以帮助...

于 2013-07-12T15:48:02.350 回答
1

我认为你应该改变 u = ml; 为 u = m -1。

它是 1 而不是 l。---------addtion------因为(l+u)可能大于2^31-1（如果int是32bits的话），所以可能会溢出。所以你应该把(l+u)/2改为l+((ul)>>1)，并且ul不能大于2^31-1。

于 2013-07-07T07:02:44.753 回答
-1

虽然 Machtl 和其他人已经写了克服溢出错误的方法，但只是为了完整性而添加

  1. 使用int mid = (low + high) >>> 1; 更快的方式
  2. 在 C 和 C++ 中（我们没有 >>> 运算符） mid = ((unsigned int)low + (unsigned int)high)) >> 1;
于 2014-01-01T05:41:58.007 回答