def binary_search(lst, val):
    """
    Find val in lst.  Return its index or -1 if not there.
    The list MUST be sorted for this to work.
    """
    
    # keep track of the first and last possible positions.
    first = 0
    last = len(lst)-1
    
    while first <= last:
        mid = (first+last)/2
        if lst[mid] == val:
            # found it
            return mid
        elif lst[mid] < val:
            # too small, only look at the right half
            first = mid+1
        else: # lst[mid] > val
            # too large, only look at the left half
            last = mid-1
    
    # if we get this far, there is no val in lst.
    return -1