INT_MAX            = 2147483647
left               = 1500000000
right              = 2000000000
true midpoint      = 1750000000
(left+right)       = 3500000000 which does not fit in int
(left+right)/2     = -397483648   <-- wrong, negative
left+(right-left)/2 = 1750000000   <-- right
