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

A straightforward implementation of the binary search algorithm.

Python, 13 lines
 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.

5 comments

Andrew Dalke 21 years, 2 months ago  # | flag

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

>

Gillian Matthews 10 years ago  # | flag

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

Karl Schärlund 10 years ago  # | flag

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.

Karl Schärlund 10 years ago  # | flag

Got my password reset email, sorry if the comment above does not make much sense any longer. :-)

Grant Jenks 9 years, 6 months ago  # | flag

Indeed! The bisect module 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.

Created by Karl Schärlund on Thu, 11 Oct 2001 (PSF)
Python recipes (4591)
Karl Schärlund's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks