binary search middle value calculation

Question

The following is the pseudocode I got from a TopCoder tutorial about binary search

binary_search(A, target):    lo = 1, hi = size(A)    while lo <= hi:       mid = lo + (hi-lo)/2       if A[mid] == target:          return mid                   else if A[mid] < target:           lo = mid+1       else:          hi = mid-1     // target was not found 

Why do we calculate the middle value as mid = lo + (hi - lo) / 2 ? Whats wrong with (hi + lo) / 2

I have a slight idea that it might be to prevent overflows but I'm not sure, perhaps someone can explain it to me and if there are other reasons behind this.

Answer 1

Yes, (hi + lo) / 2 may overflow. This was an actual bug in Java binary search implementation.

No, there are no other reasons for this.

Answer 2

Although this question is 5 years old, but there is a great article in googleblog which explains the problem and the solution in detail which is worth to share.

It's needed to mention that in current implementation of binary search in Java mid = lo + (hi - lo) / 2 calculation is not used, instead the faster and more clear alternative is used with zero fill right shift operator

int mid = (low + high) >>> 1;