以下两种不同的方式找中点有什么区别

Question

对于数组中的分而治之算法，我们需要能够找到范围的中间元素。显而易见的方法是mid = (leftSide + rightSide) / 2。但是，我听说这种方式不正确，我们需要改为编写mid = leftSide + (rightSide - leftSide) / 2。有人能解释一下这两者之间的区别吗？

Answer 1

使用可能会溢出，具体取决于您使用的语言和数据类型以及和(leftSide + rightSide) /2的值。原因是您先将它们相加，然后除以 2。leftSiderightSideleftSiderightSide

在此方法中，leftSide + (rightSide - leftSide)/2您将它们减去并除以 2，然后添加 leftSide，这在某些情况下可能会产生影响。

除此之外，这些表达式在数学上是相同的，如下所示：

leftSide + (rightSide - leftSide)/2
2leftSide/2 + (rightSide - leftSide)/2
(2leftSide + rightSide - leftSide)/2
(rightSide + leftSide)/2

根据OP的要求，我添加了一个关于如何(leftSide + rightSide) / 2溢出的具体Java示例。

假设我们在 java 中存储left和 ，它们是 4 字节有符号整数。这意味着他们覆盖到。现在，进一步假设我们有和作为我们的左和右。请记住，我们的上限仅略小于 4 字节有符号整数的上限。第一次搜索后，由于目标位于右侧，因此左侧变为，因为。此时使用该公式是危险的。因为：rightint-2^312^31-1021474830002^31-1 = 214748364710737415012147483000 / 2 + 1 = 1073741501(left + right) / 2

left =  2147483000 / 2 + 1 = 1073741501
right = 2147483000
left + right = 3221224501

因此，left + right超出了无符号 4 字节整数的可用限制/位。发生的情况是，Java 将新整数解释为负数，因为显示符号的最高有效位已设置。考虑以下示例：

leftSide + (rightSide - leftSide)/2
2leftSide/2 + (rightSide - leftSide)/2
(2leftSide + rightSide - leftSide)/2
(rightSide + leftSide)/2

输出：

1073741500 2147483647
-1073742149

长话短说，您可以通过使用来避免这种情况leftSide + (rightSide - leftSide)/2。由于先从右减去左，然后除以 2，所以不存在溢出的风险。

如果您进一步感兴趣，这里有一篇由 Google 研究工程师撰写的博客文章，介绍了二分搜索中这个错误的普遍程度。