ActiveState Code

Recipe 81188: Binary search

A straightforward implementation of the binary search algorithm.

Python 
 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

Discussion

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.

Comments

  1. 1. At 12:58 p.m. on 10 jan 2003, Andrew Dalke said:

    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

    >

Sign in to comment