#
#  binary_search(i, vals)
#
#  Parameters:
#    vals: a list of values 
#    i: a value to be searched for
#  Preconditions:
#    vals is a list that is sorted in ascending order
#    i is of the same type as all elements in vals
#  Postconditions:
#    If i exists in vals, binary_search will return 1 position that 
#                               it exists in
#    If i does not exist in vals, binary_search will return -1
def binary_search(i,vals):
                return binary_search_parser(i,vals,0, len(vals)-1)

def binary_search_parser(i,vals, start, end):
                if end-start <= 0:
                                return -1
                pivot = (start-end)/2 + start
                if vals[pivot] == i:
                                return i
                elif vals[pivot] < i:
                                return binary_search_parser(i, vals, start, pivot)
                else:
                                return binary_search_parser(i, vals, pivot, end)