为什么我们在二分搜索中写lo +(hi-lo)/ 2？

Question

我正在阅读有关二元搜索的内容......我知道找到中间价值的传统方式就像

mid=(hi+lo)/2

但我也看到,以避免溢出中间值是这样计算的

mid=lo+(hi-lo)/2

但为什么？？我找不到实际的原因.任何人都可以举例说明理由吗？它与其他问题不同,因为其他问题没有我想要的答案......

Answer 1

假设您正在使用32位unsigned int作为索引搜索4000000000元素数组.

第一步看起来好像搜索到的元素(如果存在)将位于上半部分.lo的价值是,2000000000而且hi是4000000000.

hi + lo溢出并产生小于预期值的值6000000000.它实际上产生了6000000000-2 ³².结果,(hi + lo) / 2是一个很小的价值.它甚至不在lo和之间hi!

从那时起,搜索将是错误的(它可能会得出结论,即使元素存在,元素也不存在).

与此相反,即使在此示例中的极端值,lo + (hi - lo) / 2始终计算之间的折射率中途hi和lo,如预期由算法.

Answer 2

从数学上讲，它们是等价的。

在计算机方面，mid=(hi+lo)/2操作较少，但mid=lo+(hi-lo)/2最好避免溢出。

假设您要搜索的项目接近数组的末尾，然后hi+lo接近2*size。因为size几乎与您的最大索引一样大，2*size因此hi+lo可能会溢出。