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