JAVA

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

9

//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.