integer-overflow - 为什么 left+(right-left)/2 不会溢出？

Question

在本文中:http://googleresearch.blogspot.sg/2006/06/extra-extra-read-all-about-it-nearly.html ，它提到大多数快速排序算法有一个错误(左+右)/2，并指出解决方案是使用left+(right-left)/2而不是 (left+right)/2 .
问题中也给出了解决方案Bug in quicksort example (K&R C book)?

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

Answer 1

您有 left < right根据定义。

因此，right - left > 0 ，以及 left + (right - left) = right (遵循基本代数)。

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

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