def binary_search(x, L):
    """Binary search for x in sorted list L

    Assumes x is an integer, and L a non-decreasing list of integers
    
    Returns index i, -1 <= i < len(L), where L[i] <= x < L[i+1],
    assuming L[-1] = -infty and L[len(L)] = +infty"""

    assert isinstance(x, int)
    assert isinstance(L, list)    
    assert all([isinstance(e, int) for e in L])
    assert all([L[i] <= L[i+1] for i in range(len(L)-1)])

    low, high = -1, len(L)

    while low + 1 < high:
        assert (low == -1 or L[low] <= x) and (high == len(L) or x < L[high])
        mid = (low + high) // 2
        assert isinstance(L[mid], int)
        assert (low == -1 or L[low] <= L[mid]) and (high == len(L) or L[mid] <= L[high])
        if x < L[mid]:
            high = mid
        else:
            low = mid
    result = low
    
    assert (isinstance(result, int) and -1 <= result < len(L) and
            ((result == -1 and (len(L) == 0 or x < L[0])) or
             (result == len(L) - 1 and x >= L[-1]) or
             (0 <= result < len(L) - 1 and L[result] <= x < L[result + 1])))

    return result

assert binary_search(42, []) == -1
assert binary_search(42, [7]) == 0
assert binary_search(7, [42]) == -1
assert binary_search(7, [42,42,42]) == -1
assert binary_search(42, [7,7,7]) == 2
assert binary_search(42, [7,7,7,56,81]) == 2
assert binary_search(8, [1,3,5,7,9]) == 3