Welcome, guest | Sign In | My Account | Store | Cart
1

A straightforward implementation of the binary search algorithm.

Python, 12 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12``` ```def binary_search(seq, t): min = 0; max = len(seq) - 1 while 1: 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.

1 comment

Andrew Dalke 10 years, 5 months ago

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.

``````>>> import bisect

>>> bisect.bisect_right([1, 5, 9, 12, 18, 35], 5)
``````

2

``````>>> bisect.bisect_left([1, 5, 9, 12, 18, 35], 5)
``````

1

``````>>> bisect.bisect_left([1, 5, 9, 12, 18, 35], 15)
``````

4

>