Explain the difference between these Midpoint Algorithms

Question

Why does the midpoint algorithm for Binary Search use

low + (high-low)/2

rather than

(low + high)/2

Answer 1

Your question is tagged for python, so I'll answer for python. In short, it doesn't:

https://hg.python.org/cpython/file/2.7/Lib/bisect.py

The pythonic implementation above found in the docs uses the latter construction. As people in the comments have pointed out, some languages need to respect overflow. Python isn't none of them and has arbitrary precision integers.

In the comments it was speculated that someone porting from a C-like language might copy the more acceptable construction for that language. This is possible. Someone else commented that one might be faster than the other; such a micro-optimization seems to be difficult to comment on in general.

But... what if they aren't Ints!

I have assumed that these are integers because for binary search, the indices are integers. If they are indeed not integers, then you are going to have some problems using them to access arrays. But in the mean time, you might experiene different results:

a = b = sys.float_info.max
print a + (a-b)/2 # prints a really big number
print (a+b)/2 # prints inf

Similarly,

a = b = float("inf")
print a+(a-b)/2 # prints nan
print (a+b)/2 # prints inf

That latter example is different, albeit it isn't clear to me which is better. For why this occurs, you can look at the overflow explanations in the article linked above.