binary-search - 二分查找中间值计算

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

虽然这个问题已有5年历史了，但是有一个great article in googleblog可以详细解释问题和解决方案，值得分享。

需要指出的是，在Java的当前二进制搜索实现中，不使用mid = lo + (hi - lo) / 2计算，而是使用零填充右移运算符来提供更快，更清晰的替代方法

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