3 ms·
Algorithms and Data Structures: Binary Search
- eesmith 9y agoBinary 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#Implementation_issues 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.