import random

def RL( n ):
    """ returns a list of n random ints """
    L = []
    MX = 1000000000
    for i in xrange(n):
        if i%500000 == 0:
            print "half million #", i/500000
        L.append( random.randint(0,MX) )
    return L

def BS( ):
    """ binary search in a sorted list """
    n = input( "Enter # of el's: " )
    S = RL( n )
    print "list complete"
    S.sort() # now it's sorted

    while True:
    
        val = input( "Enter a val to find: " )
        
        lo = 0
        hi = len(S)-1

        while True:

            mid = (lo + hi) / 2
            
            if S[mid] == val:
                print "True"
                break
            
            if lo >= hi:
                print "False"
                break

            if S[mid] < val:
                lo = mid+1
            else:
                hi = mid-1




            

        """
        if val in S: print True
        print False
        """