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.

import random

#------------------------------------------------------------------
def createArray( n ):
    """Creates a list of n random numbers in sorted order"""
    A= []
    for i in range( n ):
        A.append( int( random.randrange( n * 100 ) ) )
   
    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"
    """

    if low>high:
        return False, -1
   
    mid = ( low + high )/2
    if A[mid]==key:
        return True, 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 = input( "search for what number?  " )
        success, index = binsearch( A, 0, len( A )-1, key )
        if success:
            print "found %d at index %d" % ( key, index )
        else:
            print "%d not in A" % key


main()