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)
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) 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.