4
$\begingroup$

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;

instead?

$\endgroup$
  • $\begingroup$ The only "advantage" is that your calculation never exceeds the value of right. $\endgroup$ – fade2black Aug 25 '17 at 10:42
  • $\begingroup$ @fade2black, I don't see how is it possible to exceed value of right in second case. If left = right, then (2 * right) / 2 = right. $\endgroup$ – rus9384 Aug 25 '17 at 10:45
  • $\begingroup$ @rus9384 left + right >= right, intermediate values I mean. Kind of take actions against overflow. $\endgroup$ – fade2black Aug 25 '17 at 10:47
  • 2
    $\begingroup$ @fade2black, I think, this is an answer. $\endgroup$ – rus9384 Aug 25 '17 at 10:52
  • 3
    $\begingroup$ This is indeed the answer. $\endgroup$ – Raphael Aug 25 '17 at 11:15
9
$\begingroup$

Because 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 left and right and add half of that to left. This is only a single extra operation to make the algorithm more robust.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Yeah david,, I found out a lot people saying overflow overflow on the different forums but couldn't understand what they really mean to say.. After i found out the example,, my confusion was cleared.. $\endgroup$ – Bikash Gurung Sep 24 '18 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.