Algorithms and Data Structures: Binary Search

https://medium.com/@julia.geist/binary-search-algorithm-7170ae244438

by juliascript • 8 years ago

1 1 8 years ago

eesmith• 8 years ago

Binary search is one of those algorithms which seem really easy, but in practice is hard to get exactly correct. See https://en.wikipedia.org/wiki/Binary_search_algorithm#Implem... .

One of the classic problems is numeric overflow, when people compute "(lowerBound + upperBound) / 2. This implementation avoids that problem by doing "lowerBound + (upperBound — lowerBound) / 2)". However, as the code is in Python, where integers are arbitrary sized, this isn't actually a problem. I think this was copied from a C implementation; the "cast" also reveals a C background as in Python this is a conversion.

It also appears there is a mistake in this code, in the part which says

        elif x < number:
             lowerBound += 1

It should likely be lowerBound = middleIndex. As it stands, something like binarySearch(range(9), 8) will test items [4], [5], [5], [6], [6], [7], [7], before finding the value 8 at position [8].

This is the sort of error which is hard to identify without careful testing, as the code will generate the correct answer even with the wrong algorithm.

P.S. 4 submissions to the same essay during 2 days seems like excessive promotion.

Algorithms and Data Structures: Binary Search

Related Stories