I noticed that in many books calculation of midpoint for binary search uses this:
int mid = left + (right - left) / 2;
Why not use
int mid = (left + right) / 2;
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
left + right may overflow. Which then means you get a result that is less than
left. Or far into the negative if you are using signed integers.
So instead they take the distance between
right and add half of that to left. This is only a single extra operation to make the algorithm more robust.
Suppose your 'low' and 'high' are 16 bit unsigned integers. That means, they can only have a maximum value of 2^16=65536. Consider this, low = 65530 high = 65531
If we added them first, (low+high) would end up being junk since that big a number (131061) cannot be stored in a your 16-bit integer. And so, mid would be a wrong value.
This answer gives a practical example of why the
l + (r-l)/2 calculation is necessary.
In case you are curious how the two are equivalent mathematically, here is the proof. The key is adding
0 then splitting that into
l/2 - l/2.
(l+r)/2 = l/2 + r/2 = l/2 + r/2 + 0 = l/2 + r/2 + (l/2 - l/2) = (l/2 + l/2) + (r/2 - l/2) = l + (r-l)/2