Middle element of Binary Seach

Question

I saw many middle element that calculated with different ways, such as:

mid = low + (high + low)//2
mid = (low + high)/2
mid = low + (high - low)//2
mid = int((high + low)/2)

what is the correct calculation way for Python? I tired with this

Answer 1

The two that make some sense are:

mid = low + (high - low) // 2
mid = (high + low) // 2

They are mathematically equivalent, however, most proper library implementations will use the first as it does not have any intermediate results that are larger than high and thus will never cause integer overflow errors.

Note that floor division a//b is (almost) the same as int(a/b). Almost because it does not hold for negative numbers which should not matter here as list indeces are positive.

Answer 2

>>> low = 10
>>> high = 20
>>> low + (high + low)//2
25
>>> (low + high)/2
15.0
>>> low + (high - low)//2
15
>>> int((high + low)/2)
15

It depends on what you want to get... in this case only the last two make sense.

Answer 3

Of those four, only mid = low + (high - low)//2 is correct. You missed the best one: mid = (low + high) // 2. It's simpler and saves one operation, and you do binary search for speed. Python's own bisect also does it: mid = (lo + hi) // 2.