# recursive binary search in a list
#
from random import uniform
import time
def recBinSearch(A, x, low, high):
global count_comp # declare count_comp as a gloabal variable
if low > high: # No place left to look, return -1
return -1
mid = (low + high) / 2
item = A[mid]
count_comp = count_comp + 1
if item == x: # Found it! Return index
return mid
elif x < item: # recurse looking in lower half
return recBinSearch(A, x, low, mid-1)
else: # recurse looking in upper half
return recBinSearch(A, x, mid+1, high)
def search(A, x):
# function search sets up the recursion
return recBinSearch(A, x, 0, len(A)-1)
if __name__ == "__main__":
# set up a sorted list with uniform distribution
n = 1000000
A = [0]*n
for i in range(n):
A[i] = int(uniform(0,2*n))
A.sort()
# choose an element to search for
x = int(uniform(0,2*n))
print "searching for element x = ", x
print
# using the recursive binary search function
count_comp = 0 # count number of comparisons made by recBinSearch
start = time.clock()
found = search(A,x)
end = time.clock()
print "Binary search found the element at index ", found, "after ", count_comp, "number of comparisons"
print "using", end-start, "seconds"
print "using %f seconds" % (end-start) # see Zelle pages 103&104 for printing in this foprmat
print
# using a built-in Python feature
start = time.clock()
print "Python search feature"
if x in A:
print "found the element"
end = time.clock()
print "using", end-start, "seconds"
print "using %f seconds" % (end-start)