二分搜索中值计算

Question

以下是我从TopCoder关于二进制搜索的教程中得到的伪代码

binary_search(A, target):
   lo = 1, hi = size(A)
   while lo <= hi:
      mid = lo + (hi-lo)/2
      if A[mid] == target:
         return mid            
      else if A[mid] < target: 
         lo = mid+1
      else:
         hi = mid-1

   // target was not found

为什么我们计算中间值为mid = lo +(hi-lo)/ 2？(hi + lo)/ 2错了

我有一点想法,可能是为了防止溢出,但我不确定,也许有人可以向我解释,如果还有其他原因.

Answer 1

是的,(hi + lo)/ 2可能会溢出.这是Java二进制搜索实现中的实际错误.

不,没有其他原因.

Answer 2

虽然这个问题已经有5年了,但googleblog上有一篇很棒的文章解释了这个问题和解决方案,这个问题值得分享.

需要提一下的是,目前在Java mid = lo + (hi - lo) / 2计算中的二进制搜索实现并未使用,相反,使用零填充右移运算符的更快更清晰的替代方案

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

Answer 3

从后面的同一个教程:

"你也可能想知道为什么mid使用mid = lo +(hi-lo)/ 2而不是通常的mid =(lo + hi)/ 2来计算.这是为了避免另一个潜在的舍入错误:在第一种情况下,我们希望除法总是向下舍入,朝向下界.但是除法截断,所以当lo + hi为负时,它将开始向更高的边界四舍五入.以这种方式编码计算确保分割的数字总是正的因此我们总是按照我们的要求进行舍入.虽然当搜索空间只包含正整数或实数时,错误不会出现,但我决定在整篇文章中以这种方式对其进行编码以保持一致性."

Answer 4

确实可以(hi+lo)溢出整数.在改进的版本,它可能看起来从喜减去LO,然后再次将其添加是毫无意义的,但有一个原因是:在执行此操作不会溢出整数和它将导致具有相同的数的奇偶校验为hi+lo,使得剩余的(hi+lo)/2将是相同的(hi-lo)/2.然后可以在分割后安全地添加lo以达到相同的结果.

Answer 5

假设我们正在搜索的数组的长度为 INT_MAX。因此最初：

high = INT_MAX 
low = 0

在第一次迭代中，我们注意到目标元素大于中间元素，因此我们将起始索引移动到 mid ，如下所示

low = mid + 1

在下一次迭代中，计算 mid 时，计算公式为 (high + low)/2，本质上转换为 INT_MAX + low(which is half of INT_MAX + 1) / 2

现在，该操作的第一部分（即（高 + 低））将导致溢出，因为我们将超过最大 Int 范围（即 INT_MAX）