CSC231 binarySearch.py

--D. Thiebaut 18:03, 23 November 2008 (UTC)

---

#! /usr/bin/python
# binarySearch.py
# D. Thiebaut
# searches and array using recursive binary search


def search( key, A, left, right ):
    """The recursive function"""
    if left > right:
        return -1

    mid = ( left + right ) / 2
    if A[mid] == key:
        return mid

    if key < A[mid]:
        return search( key, A, left, mid-1 )
    else:
        return search( key, A, mid+1, right )

def main():
    """Creates an array and allows user to search it""" 
    A = [1, 3, 10, 4, -1, 10, -20, 100, 12, 13, 15, 5, 6]
    A.sort( )
    print A
    
    while True:
        try:
            key = input( "Enter key (Press Enter to stop)> " )
        except:
            break

        index = search( key, A, 0, len( A )-1 )
        if index==-1:
            print "not found!"
        else:
            print "found %d at Index %d" % ( key, index )

main()