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

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.

Suppose (to make the example easier) the maximum integer is 100, left = 50, and right = 80. If you use the naive formula:

int mid = (left + right)/2;

the addition will result in 130, which overflows.

If you instead do:

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

you can't overflow in (right - left) because you're subtracting a smaller number from a larger number. That always results in an even smaller number, so it can't possibly go over the maximum. E.g. 80 - 50 = 30.

And since the result is the average of left and right, it must be between them. Since these are both less than the maximum integer, anything between them is also less than the maximum, so there's no overflow.

Basic logic.

1. by definition left <= MAX_INT
2. by definition right <= MAX_INT
3. left+(right-left) is equal to right, which already is <= MAX_INT per #2
4. and so left+(right-left)/2 must also be <= MAX_INT since x/2 is always smaller than x.

Compare to the original

1. by definition left <= MAX_INT
2. by definition right <= MAX_INT
3. therefore left+right <= MAX_INT
4. and so (left+right)/2 <= MAX_INT

where statement 3 is clearly false, since left can be MAX_INT (statement 1) and so can right (statement 2).