why left+(right-left)/2 will not overflow?

Question

In this article: http://googleresearch.blogspot.sg/2006/06/extra-extra-read-all-about-it-nearly.html, it mentioned most quick sort algorithm had a bug (left+right)/2, and it pointed out that the solution was using left+(right-left)/2 instead of (left+right)/2. The solution was also given in question Bug in quicksort example (K&R C book)?

My question is why left+(right-left)/2 can avoid overflow? How to prove it? Thanks in advance.

Answer 1

You have left < right by definition.

As a consequence, right - left > 0, and furthermore left + (right - left) = right (follows from basic algebra).

And consequently left + (right - left) / 2 <= right. So no overflow can happen since every step of the operation is bounded by the value of right.

---

By contrast, consider the buggy expression, (left + right) / 2. left + right >= right, and since we don’t know the values of left and right, it’s entirely possible that that value overflows.