修复Bentley的书中的二进制搜索错误(编程珍珠:编写正确的程序)

Question

二进制搜索可以通过多种方式实现 - 递归,迭代,条件等.我从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中发现了一个错误; 它可能导致溢出.我们怎样才能避免这种二进制搜索中的溢出？

Answer 1

请尝试以下方法:

更改

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仍然是相同的,2^31 / 2因此l l + u将导致溢出.

这样我们就可以u + l通过首先确定l和u之间的相对中间值(u - l) / 2然后将较低的数字l加到它来避免添加,这样它就变成了绝对的.所以在操作过程中m = (u-l) / 2 + l;我们永远不会超过你的价值.

总结完整的代码:

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;
     }
}

Answer 2

假设l和u int都属于[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;
        }
    }

Answer 3

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

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

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

当然，这与 32 位 Java 完全相同。您需要 64 位 Java 的破碎组合——一种允许大小接近 2^64 的对象但将索引限制为 2^32-1 以导致出现此“错误”的语言。

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