二分查找中间值计算

问题描述

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

The following is the pseudocode I got from a TopCoder tutorial about binary search

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

Why do we calculate the middle value as mid = lo + (hi - lo) / 2 ? Whats wrong with (hi + lo) / 2

我有一个轻微的想法，那就是防止溢出，但是我不确定，也许有人可以向我解释一下，以及背后是否还有其他原因.

I have a slight idea that it might be to prevent overflows but I'm not sure, perhaps someone can explain it to me and if there are other reasons behind this.

推荐答案

尽管此问题已有5年历史，但存在 googleblog中的出色文章，其中详细介绍了问题和解决方案，值得分享.

Although this question is 5 years old, but there is a great article in googleblog which explains the problem and the solution in detail which is worth to share.

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

It's needed to mention that in current implementation of binary search in Java mid = lo + (hi - lo) / 2 calculation is not used, instead the faster and more clear alternative is used with zero fill right shift operator

这篇关于二分查找中间值计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！