在二进制搜索计算中旬

我在读这有二进制搜索以下算法的算法书：在二进制搜索计算中旬

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

我看不出会如何导致溢出。当我在脑海中为一些不同的输入运行算法时，我没有看到中间值超出数组索引。

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

来源

2011-07-18 Bharat

加法，减法，乘以2的数字都会产生更多的位，所以很明显会有溢出的机会 –

[二分查找中值计算]可能重复（http://stackoverflow.com/questions/4534342/binary-search-中间值计算） –

这个post涵盖了这个着名的bug在很多细节。正如其他人所说，这是一个溢出问题。推荐链接修复的方法是如下：

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范围执行二进制搜索。

来源

2011-07-18 15:27:00

您提供的链接对问题有明确的解释。谢谢！ – Bharat

+1为有趣的链接。 –

潜在的溢出本身就是l+u。

这实际上是在JDK中进行二进制搜索的a bug in early versions。

来源

2011-07-18 15:24:29 Nemo

链接中断 – jdhao

@jdhao - 当时正在工作。可接受的答案有一个链接到一个完整的帐户的作者的错误代码。无论如何，我已经更新了我的链接。 – Nemo

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

来源

2011-07-18 15:24:57 murgatroid99

杰夫建议真的很好post阅读有关此错误，这里是总结，如果你想快速概述。

在编程珍珠宾利说，类似的行“将m设置为l和u的平均值，截短到最接近的整数。”从表面上看，这个断言可能看起来是正确的，但是对于大的int变量值低和高而言失败。具体而言，如果低位和高位的总和大于最大正整数值（2^31 - 1），则失败。总和溢出为负值，并且该值在除以二之后保持负值。在C中，这会导致数组索引出现不可预知的结果。在Java中，它引发ArrayIndexOutOfBoundsException。

来源

2015-07-25 13:42:08 Vipin

在二进制搜索计算中旬

回答

相关问题