#Chapter 45 Binary search (iterative)

def binarySearch(aList,itemSought, first, last):
    while first <= last:
        midpoint = (last + first)//2
        if aList[midpoint] == itemSought:
            return midpoint
        elif aList[midpoint] < itemSought:
            first = midpoint + 1
        else:
            last = midpoint - 1
        #endif
    #endwhile
    return -1

#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)