为什么左+(左右)/2不会溢出

Question

在这篇文章中：http://googleresearch.blogspot.sg/2006/06/extra-extra-read-all-about-it-nearly.html，它提到大多数快速排序算法都有一个错误（左+右）/2，并指出解决方案使用的是left+(right-left)/2而不是(left+right)/2。解决方案也给出了问题快速排序示例中的错误（K&R C书）？

我的问题是为什么left+(right-left)/2可以避免溢出？如何证明呢？提前谢谢。

Answer 1

根据

定义，您必须left < right。

因此，right - left > 0，而且left + (right - left) = right（从基本代数开始）。

因此left + (right - left) / 2 <= right.因此不会发生溢出，因为操作的每一步都受 right 的值限制。

---

相比之下，考虑错误的表达式，(left + right) / 2 。 left + right >= right，由于我们不知道left和right的值，该值完全有可能溢出。

Answer 2

假设（为了使示例更容易）最大整数为 100，left = 50 和 right = 80 。如果您使用朴素公式：

int mid = (left + right)/2;

添加将导致溢出的130。

如果您改为执行以下操作：

int mid = left + (right - left)/2;

您不能在(right - left)中溢出，因为您要从较大的数字中减去较小的数字。这总是导致更小的数字，因此它不可能超过最大值。例如 80 - 50 = 30 .

由于结果是 left 和 right 的平均值 ，它必须在它们之间。由于它们都小于最大整数，因此它们之间的任何内容也小于最大值，因此没有溢出。

Answer 3

基本逻辑。

1. 根据定义left <= MAX_INT
2. 根据定义right <= MAX_INT
3. left+(right-left) 等于 right ，这已经是 <= MAX_INT 每个 #2
4. 因此left+(right-left)/2也必须<= MAX_INT，因为x/2总是小于x.

与原版相比

1. 根据定义left <= MAX_INT
2. 根据定义right <= MAX_INT
3. 因此left+right <= MAX_INT
4. 等等(left+right)/2 <= MAX_INT

其中语句 3 显然是假的，因为left可以MAX_INT（语句 1），也可以right（语句 2）。

Answer 4

由于 int 数据类型在 Java 中为 32 位（假设编程语言），任何超过 32 位的值都会被滚动更新。在数字方面，这意味着在 Integer.MAX_VALUE （2147483647） 上递增 1 后，返回的值将为 -2147483648。

来到上面的问题，让我们假设以下几点：

int left = 1;
int right = Integer.MAX_VALUE;
int mid;

案例1：

mid = (left +right)/2; 
//Here the value of left + right would be -2147483648 which would overflow.

案例2：

mid = left + (right - left)/2;
//This would not have the same problem as above as the value would never exceed "right".

理论上：

两个值都与左 + （右 - 左）/2 = （2*左 + 右 - 左）/2

= （左 + 右）/2 相同

希望这能回答你的问题。

Answer 5

一个简单的工作示例将显示它。 为简单起见，假设数字溢出 999 以上。 如果我们有：

left = 997
right = 999

然后：

left + right = 1996

在我们到达/2之前已经飞过了. 然而：

right - left = 2
(right-left)/2 = 1
left + (right-left)/2 = 997 + 1 = 998

因此，我们避免了溢出。

更一般地说（正如其他人所说）：如果left和right都在范围内（假设right > left，那么(right-left)/2将在范围内，因此也必须left + (right-left)/2，因为这必须小于right（因为您left增加了一半它与right之间的差距。

Answer 6

（这与其说是证明，不如说是直观的解释。

假设您的数据是unsigned char的，并且left = 100和right = 255（因此right在范围的边缘）。如果你做left + right，你会得到 355，这不符合unsigned char范围，所以它会溢出。

然而，(right-left)/2是一个X使得left + X < right < MAX的量，其中MAX是 255 表示unsigned char。这样，您可以确保总和永远不会溢出。

Answer 7

为什么不是 m = （l - r）/2？由于我们不需要已经遍历的索引，从开始到现在的左边在哪里？