CSC111 BinarySearch.py

--D. Thiebaut 13:05, 26 April 2010 (UTC)

---

# binarySearch.py
# D. Thiebaut
#
# Searches a sorted array of random numbers for a number.

from random import randrange

#------------------------------------------------------------------
def createArray( n ):
    """Creates a list of n random numbers in sorted order"""
    A= []
    for i in range( n ):
        A.append( randrange( n * 10 )  )
    
    A.sort()
    return A

#------------------------------------------------------------------
def binsearch( A, low, high, key ):
    """a recursive function that searches the list A to see if
    it contains the item key between the indexes "low" and "high".
    returns the index where the key was found, or -1 otherwise
    """

    if low>high:
        return -1
    
    mid = ( low + high )/2
    if A[mid]==key:
        return mid

    if key < A[mid]:
        return binsearch( A, low, mid-1, key )
    else:
        return binsearch( A, mid+1, high, key )


#------------------------------------------------------------------
def main():
    """prompts the user for a number and returns wether the number is
    in the list or not"""
    
    A = createArray( 20 )
    print( A )

    while True:
        print
        key = int( input( "search for what number?  " ) )
        index = binsearch( A, 0, len( A )-1, key )
        if index != -1:
            print( "found %d at index %d" % ( key, index ) )
        else:
            print(  "%d not in A" % key )


main()