为什么在二分查找中要写成lo+(hi-lo)/2？

Question

我在阅读有关二分查找的内容...我知道传统的查找中间值的方法是这样的：

mid=(hi+lo)/2

但我也看到为了避免溢出，中间值是这样计算的。

mid=lo+(hi-lo)/2

但是为什么呢？我找不到实际的原因...有人能给我一个带有例子的解释吗？与其他问题不同，因为其他问题没有像我想要的带有例子的答案...

- user2291995

---

答案已经在你的问题中了，为了避免溢出。 - harold

这个问题不适合讨论，因为它是一个带有问号的回答。 - Quentin

我没有得到任何例子..我想要例子.. - user2291995

假设 hi 和 lo 是指针（或在 C++ 中是迭代器）。两个指针的和没有意义，但是两个指针的差是一个整数。将整数添加到指针也是有意义的。 - user515430

Answer 1

假设你正在使用32位无符号整数作为索引，在搜索一个长度为4000000000的数组。

第一步似乎表明，如果存在要查找的元素，则它将在数组的上半部分。lo的值为2000000000，hi的值为4000000000。

hi + lo会溢出，并产生一个比预期的6000000000小的值。实际上，它产生了6000000000-2 ^ 32。因此，(hi + lo) / 2是一个很小的值。它甚至不在lo和hi之间！

从那时起，搜索将会失败（即使元素存在，它也可能会得出元素不存在的结论）。

相比之下，即使在这个例子中出现极端值，lo + (hi - lo) / 2始终计算出在hi和lo之间的索引，这正是算法所需要的。

- Pascal Cuoq

---

@ikegami 因为我选择了 unsigned int 类型，所以这个加法不是未定义行为，而是被定义为产生环绕结果。 - Pascal Cuoq

有趣。谢谢。 - ikegami

这个问题更可能在16位架构统治地球的时候浮出水面。 - Mark Ransom

Google工程师在2006年重新发现了32位的这个问题：http://googleresearch.blogspot.fr/2006/06/extra-extra-read-all-about-it-nearly.html - Pascal Cuoq

Answer 2

数学上讲，它们等同。

在计算机术语中，“mid=(hi+lo)/2” 的操作较少，但“mid=lo+(hi-lo)/2” 更受欢迎以避免溢出。

例如，如果您要搜索的项目靠近数组末尾，则“hi+lo”将接近“2*size” 。由于“size”几乎可以与最大索引一样大，“2*size”和因此“hi+lo”可能会溢出。

- ikegami

---

“hi + lo” 可能会溢出。如果 “lo, hi” 是范围内的正整数且 “lo <= hi”，则 “lo+(hi-lo)/2” 永远不会溢出。 - a06e

数值溢出与可寻址空间的大小无关，而与数值类型可以表示的范围有关。 - Mike Seymour

@Mike Seymour，已经修复。 - ikegami