A straightforward implementation of the binary search algorithm.
Python, 13 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 | def binary_search(seq, t):
min = 0
max = len(seq) - 1
while True:
if max < min:
return -1
m = (min + max) // 2
if seq[m] < t:
min = m + 1
elif seq[m] > t:
max = m - 1
else:
return m
|
Binary search is a fast algorithm for searching sorted sequences. It runs in about log2 N time, as opposed to an average run time of N/2 for linear search. For large lists that you need to search multiple times, it might well be more efficient to sort and use binary search instead of sticking to a linear search.
Binary search is described in every introductory book on algorithms I have encountered, and is very well documented. There are som pitfalls in implementing it, though, and Jon Bentley discusses this in his wonderful book "Programming Pearls". Thats Pearls, not Perl. Recommended reading.
Revision 2 is updated to use floor division as suggested by Gillian Matthews.
Tags: algorithms
available in a standard python module. There's a standard Python library for binary searches, 'bisect.' Tim Peters once called this the best underused Python module.
2
1
4
this is a useful demonstration of the algorithm but the line = (min + max) / 2 should use integer division m = (min + max)//2 because m needs to be an integer not a float
Indeed, thanks for pointing that out!
In my defense (I wrote the recipe, but I have lost my original account details and also changed my surname...), the recipe was written a couple of months before the introduction of the floor division operator. :-)
Also, as Andrew pointed out, in practice it's better to use the bisect module.
Got my password reset email, sorry if the comment above does not make much sense any longer. :-)
Indeed! The
bisectmodule is very powerful. It's the basis for the sortedcontainers module which implements sorted list, sorted set, and sorted dict data types in pure-Python but is fast-as-C implementations. Read the implementation details for a description if interested.