A straightforward implementation of the binary search algorithm.
1 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.