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

Question

Hello, I was looking at a C ++ solution to the question "Suppose a sorted array rotates with some support unknown to you (that is, 0 1 2 4 5 6 7 can become 4 5 6 7 0 1 2). How can you find an element in rotated array efficiently? You can assume that there is no duplicate 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 that the comment says that using M = L + ((R - L) / 2) instead of M = (L + R) / 2 avoids overflow. Why is this? thanks ahead

Answer 1

Because he...

Suppose you use unsigned characters (the same goes for large integers).

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

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

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

Second, on the other hand:

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

No overflow.

As @ user2357112 noted in the comment, there are no free dinners. If L is negative, the second version may not work while the first is.

Answer 2

Not sure, but if the maximum limit of int is 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 

but

 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 run into overFlow, THEORETICAL.

I hope this analogy helps

Answer 3

The comment is incorrect for several reasons.

• For a particular problem, the risk of overflow is probably zero.
• Reordering calculations do not guarantee that the compiler will execute them in that order.
• If there is a range of values ​​for which ordering can cause an overflow, then there is another range of values ​​for which a reordered calculation will cause overflow.
• If overflow can be a problem, then this should be controlled explicitly, not implicitly.

This is a great place to approve. In this case, the algorithm is only valid if N less than half the maximum positive range of int , so say it in the statement.

If the algorithm should work for the entire positive range of signed int , then the range should be explicitly checked in the statement, and the calculation should be ordered by entering a point in the sequence (for example, split into two statements).

The exercise of this right is difficult. Numerical calculation is full of this material. Best avoided if possible. And do not take random advice (even that!) Without doing your own research.

Answer 4

It avoids overflow in this particular implementation, which works under guarantees that L and R non-negative and L <= R Under these guarantees, it should be obvious that R - L not overflowing, and L + ((R - L) / 2) also not overflowing.

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