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.