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.
1 comment
[ 4.6 ms ] story [ 14.9 ms ] threadOne 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
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.