How do you implement binary search so that it is correct on the first try, and what are the common mistakes?
You keep two bounds, the low one and the high one, and you cut the search space in half every round.
def binary_search(values, target):
low, high = 0, len(values) - 1
while low <= high:
mid = low + (high - low) // 2
if values[mid] == target:
return mid
if values[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
So what are the common mistakes? Here are the four that catch people out.
The first one is using low < high instead of low <= high in the loop. That version misses the last element of the list, because when the target is at the very end the loop stops before it is checked.
The second one is moving the wrong bound. When the value in the middle is smaller than the target then the target must be to the right, so the low bound moves to mid + 1. And when the value is bigger then the target is to the left, so the high bound moves to mid - 1. Getting these two the wrong way round means the search never ends properly.
The third one is using (low + high) // 2. That works on small lists, but it can overflow on a very large range of numbers in some languages. The safe form is low + (high - low) // 2, and it gives the same answer every time.
The fourth one is forgetting that the list must be sorted. Binary search is only correct on a sorted list. If the list is not in order, the comparison in the middle tells you nothing about which half to keep.
the mistake what happens
------------------------------ ---------------------------------
low < high the last element is never checked
low = mid the same element is checked again
high = mid the same element is checked again
(low + high) // 2 it can overflow on big numbers
And the complexity is O of log n for the time, because the search space is halved every round, and O of 1 for the space.
The next two questions in this topic show the versions that find the first and the last position.