c++ - 为什么我们在二分查找中写 lo+(hi-lo)/2？

Question

这个问题在这里已经有了答案:

Calculating mid in binary search (13 个回答)

关闭 8年前。

我正在阅读二进制搜索...我知道查找中间值的传统方法就像

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 之间的索引，按照算法的意图。