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

Question

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

Answer 1

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

而在此方法中 leftSide + (rightSide - leftSide)/2 将它们减去并除以 2，然后加上 leftSide，这在某些情况下会有所不同。

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

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

应 OP 的要求，我正在添加一个具体的 Java 示例，说明 (leftSide + rightSide) / 2 如何溢出。

假设我们将 left 和 right 存储在 java int 中，它们是 4 字节有符号整数。这意味着它们涵盖 -2^31 到 2^31-1。现在，进一步假设我们有 0 和 2147483000 作为我们的左右。请记住，我们的上限仅略小于 4 字节有符号整数的上限 2^31-1 = 2147483647。第一次搜索后，由于target在右边，左边变成1073741501，因为2147483000 / 2 + 1 = 1073741501。现在在这一点上使用公式 (left + right) / 2 是危险的。因为：

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

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

public class Main
{
    public static void main(String[] args) {
        
        int right = 2147483647;
        int left = 1073741500;
        
        System.out.println(left + " " + right);
        System.out.println(left + right);
    }
}

输出：

1073741500 2147483647
-1073742149

长话短说，你可以使用leftSide + (rightSide - leftSide)/2来避免这种情况。由于先从右减左再除以 2，因此没有溢出的风险。

如果您有进一步的兴趣，here's a blog post 一位 Google 研究工程师可以了解此错误在二进制搜索中的普遍程度。

Answer 2

请注意，对于所有 L 和 R，

(L + R) / 2 = (2.L - L + R) / 2 = L + (R - L) / 2.

使用整数运算。因此没有区别（除了溢出或负数的情况；然后即使除以 2 或右移也可能产生不同的结果）。

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

What is the difference between finding the mid in the following two different ways

algorithm

divide-and-conquer