#Chapter 45 Binary search (recursive)

def binarySearch(aList,itemSought, first,last):
    if last < first:
        return -1
    else:
        midpoint = (first + last)//2
        if aList[midpoint] > itemSought:  #key is in first half of list
            return binarySearch(aList, itemSought, first, midpoint-1)
        elif aList[midpoint] < itemSought:
            return binarySearch(aList, itemSought,  midpoint+1, last)
        else:
            return midpoint
        #endif

#endsub

#main
a = [1,3,4,7,9,12,15,17,28,29,35,43,46,50]
first = 0
last = len(a)-1
searchFor = int(input("Please enter key to search for: "))
i = binarySearch(a, searchFor, first,last)
if i == -1:
    print("Key not in list")
else:
    print (a[i], " is at index",i)