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

Binary search and insert in Python (Python recipe) by Noah Spurrier
ActiveState Code (http://code.activestate.com/recipes/54159/)

This demonstrates a simple binary search through sorted data. A binary search is a basic algorithm provided by bisect in Python. The binary search can be summarized by two lines of code: list.sort() item_insert_point = bisect.bisect (list, item)

Python, 35 lines
Download
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#!/usr/bin/env python
# This demonstrates a binary search through sorted data using bisect.
# A large array of random numbers is generated and then sorted.
# The the application shows where a given number would be inserted
# in the random data list.

from bisect import bisect
from random import randrange
import sys

# Get the given number from the command line argument.
# If the command line argument does not work then use a random number.
try:
    number = int(sys.argv[1])
except:
    print 'A number was not given, so a random number will be used.'
    number = randrange(10000000)

# Generate a sorted list of 100 thousand random numbers.
print 'Generating sorted random list...'
list = []
for i in range (0,100000):
    list.append(randrange(10000000))

# This does all the work.
list.sort()
insert_point = bisect (list, number)

# Show where number would be inserted.
print
print 'list[%d]=%d' % (insert_point - 1, list[insert_point - 1])
print ' > %s goes here <' % (number)
print 'list[%d]=%d' % (insert_point, list[insert_point])

# End.

A friend of mine was searching a large file for missing lines. A linear searching was taking forever. A binary search was needed. The name of the bisect module mislead him into believing that Python did not have a binary search algorithm included. I created this example to show how simple it is.

Tags: search

1 comment

Kermit Rose 15 years, 4 months ago  # | flag

The Author should make clear what work the "bisect" function is doing.

This is because the name "bisect" suggests to the unexperienced programmer that all it does is to find some middle point, one single step within a binary search loop.

I recommend that the author point out that the actual work of maintaining the list in sorted order is done by the "list.sort()", and that the "bisect" actually does the binary sort.

It would also help if the author inserted code to pull the inserted point out of the list.

I make these recommendations so that the naive reader will be less likely to jump to the conclusion that this example is incomplete.

Kermit Rose kermit@polaris.net