为什么我们在二分搜索中写lo +（hi-lo）/ 2？ [英] Why we write lo+(hi-lo)/2 in binary search?

问题描述

我正在阅读关于二进制搜索...我知道，找到中间值的传统方式是

I was reading about binary search...I know that the traditional way of finding mid value is like

mid=(hi+lo)/2

但我也看到，为了避免溢出中间值计算

But i also see that to avoid overflow mid value is calculated like that

mid=lo+(hi-lo)/2

但是为什么？我找不到实际的原因。可以任何人给我的原因与示例？
它不同于其他问题，因为其他问题没有我想要的答案，例如...

But why?? I couldn't find the actual reason..Can anyone give me the reason with example?? It is different from other question because other questions didn't have the answer that i wanted with example...

推荐答案

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

Suppose you are searching a 4000000000-element array using 32-bit unsigned int as indexes.

步骤使它看起来好像搜索元素（如果存在）将在上半部分。 lo 的值为 2000000000 和 hi 4000000000 。

The first step made it appear as though the searched element, if present, would be in the top half. lo's value is 2000000000 and hi's is 4000000000.

hi + lo 值小于预期的 6000000000 。它实际上产生6000000000-2 ³² 。因此，（hi + lo）/ 2 是一个小值。它甚至不在 lo 和 hi 之间！

hi + lo overflows and produces a value smaller than the intended 6000000000. It actually produces 6000000000-2³². As a result, (hi + lo) / 2 is a small value. It is not even between lo and hi!

相比之下，即使在这个极端值的情况下，这个元素也是不存在的。例如， lo +（hi-lo）/ 2 总是计算 hi 和 lo 。

By contrast, even with the extreme values in this example, lo + (hi - lo) / 2 always computes an index halfway between hi and lo, as intended by the algorithm.

这篇关于为什么我们在二分搜索中写lo +（hi-lo）/ 2？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！