Why M = L + ((R - L) / 2) instead of M=(L+R)/2 avoid overflow in C++?

Question

Hello I was looking at the C++ solution to the question "Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). How do you find an element in the rotated array efficiently? You may assume no duplicate exists in the array."

int rotated_binary_search(int A[], int N, int key) {
    int L = 0;
    int R = N - 1;

    while (L <= R) {
    // Avoid overflow, same as M=(L+R)/2
        int M = L + ((R - L) / 2);
        if (A[M] == key) return M;

    // the bottom half is sorted
        if (A[L] <= A[M]) {
            if (A[L] <= key && key < A[M])
                R = M - 1;
            else
                L = M + 1;
        }
    // the upper half is sorted
        else {
            if (A[M] < key && key <= A[R])
                L = M + 1;
            else 
                R = M - 1;
        }
    }
    return -1;
}

and saw the comment says that using M = L + ((R - L) / 2) instead of M=(L+R)/2 avoid overflow. Why is that? Thx ahead

Answer 1

Because it does...

Let's assume for a minute you're using unsigned chars (same applies to larger integers of course).

If L is 100 and R is 200, the first version is:

M = (100 + 200) / 2 = 300 / 2 = 22

100+200 overflows (because the largest unsigned char is 255), and you get 100+200=44 (unsigned no. addition).

The second, on the other hand:

M = 100 + (200-100) / 2 = 100 + 100 / 2 = 150

No overflow.

As @user2357112 pointed out in a comment, there are no free lunches. If L is negative, the second version might not work while the first will.

Answer 2

Not sure, but if the max limit of int is suppose 100.

R=80 & L = 40
then, 
M=(L+R)/2
M=(120)/2, here 120 is out limits if our integer type, so this causes overflow

However,

M = L + ((R - L) / 2)  
M = 80 +((40)/2)
M = 80 +20
M =100.

So in this case we never encounter a value that exceeds the limits of our integer type.So this approach will never encounter a overFlow, THEORATICALLY.

I hope this analogy will help

Answer 3

It avoids overflow in this specific implementation, which operates under the guarantees that L and R are non-negative and L <= R. Under these guarantees it should be obvious that R - L does not overflow and L + ((R - L) / 2) does not overflow either.

In general case (i.e. for arbitrary values of L and R) R - L is as prone to overflow as L + R, meaning that this trick does not achieve anything.