NOT_FOUND = -1

# Returns index of the first occurence of key in the sorted list v,
# or -1 if key is not found.
# If the list isn't sorted the behavior is undefined.
# Time complexity: O(log n), where n = len(v).
def search(v, key):
    if len(v) == 0:
        return NOT_FOUND
    return _binSearch(v, 0, len(v) - 1, key)

# Returns index of the first occurence of key in the sorted list
# v[first..last], or -1 if key is not found.
# Precondition: first <= last.
def _binSearch(v, first, last, key):
    if first == last:
        if key == v[first]:
            return first
        return NOT_FOUND

    # sublist with more than one element
    mid = (first + last)//2
    if key <= v[mid]:
        return _binSearch(v, first, mid, key)
    return _binSearch(v, mid + 1, last, key)

def test():
    min = -10
    max = 10
    v10 = [min, min, -1, -1, 0, 1, 1, max, max, max]
    tests = [
        [v10, min, 0], # [sorted list, key, expected result]
        [v10, -1, 2],
        [v10, 0, 4],
        [v10, 1, 5],
        [v10, max, 7],
        [v10, -1000, NOT_FOUND],
        [v10, 1000, NOT_FOUND],

        [[], 0, NOT_FOUND],

        [[1], 0, NOT_FOUND],
        [[1], 1, 0],
        [[1], 2, NOT_FOUND],

        [[1, 3], 0, NOT_FOUND],
        [[1, 3], 1, 0],
        [[1, 3], 2, NOT_FOUND],
        [[1, 3], 3, 1],
        [[1, 3], 4, NOT_FOUND],

        [[1, 1], 0, NOT_FOUND],
        [[1, 1], 1, 0],
        [[1, 1], 2, NOT_FOUND],

        [[1, 3, 5], 0, NOT_FOUND],
        [[1, 3, 5], 1, 0],
        [[1, 3, 5], 2, NOT_FOUND],
        [[1, 3, 5], 3, 1],
        [[1, 3, 5], 4, NOT_FOUND],
        [[1, 3, 5], 5, 2],
        [[1, 3, 5], 6, NOT_FOUND],

        [[1, 1, 3], 0, NOT_FOUND],
        [[1, 1, 3], 1, 0],
        [[1, 1, 3], 2, NOT_FOUND],
        [[1, 1, 3], 3, 2],
        [[1, 1, 3], 4, NOT_FOUND],

        [[1, 3, 3], 0, NOT_FOUND],
        [[1, 3, 3], 1, 0],
        [[1, 3, 3], 2, NOT_FOUND],
        [[1, 3, 3], 3, 1],
        [[1, 3, 3], 4, NOT_FOUND],

        [[1, 1, 1], 0, NOT_FOUND],
        [[1, 1, 1], 1, 0],
        [[1, 1, 1], 2, NOT_FOUND]
    ]

    for t in tests:
        v = t[0]
        key = t[1]
        res = search(v, key)
        expRes = t[2]
        if res != expRes:
            print("search(" + str(v) + ", " + str(key) + ") = " \
            + str(res) + "; want " + str(expRes))

test()