# Arup Guha
# 7/23/2013
# Recursive Binary Search

import random

DEBUG = False

def main():

    myList = makeList(20, 1, 100)
    myList.sort()
    print(myList)

    while True:
        
        val = int(input("What do you want to search for?\n"))
        if binsearch(myList, 0, len(myList)-1, val): 
            print("Your number is in the list.")
        else:
            print("Your number is NOT in the list.")

        ans = input("Do you want to ask again(y/n)?\n")
        if ans != "y":
            break
        
# Creates a list with numterms elements randomly in between
# low and high, inclusive.
def makeList(numterms,low,high):

    ans = [0]*numterms
    for i in range(len(ans)):
        ans[i] = random.randint(low, high)

    return ans

# Returns true iff numbers[low,high] contains searchval.
# Note: numbers must be sorted.
def binsearch(numbers,low,high,searchval):

    if DEBUG:
        print("low =",low,"high =",high,"mid=",(low+high)//2)

    # Empty search space.
    if low > high:
        return False
    
    mid = (low+high)//2

    # Go left
    if searchval < numbers[mid]:
        return binsearch(numbers, low, mid-1, searchval)

    # Go right
    elif searchval > numbers[mid]:
        return binsearch(numbers, mid+1, high, searchval)

    # Found it!
    else:
        return True
        
main()