from math import floor

def find_magic_index_brute(xs):
    for i in range(len(xs)):
        if xs[i] == i:
            return i
    return -1

def mid(lo, hi):
    return lo + floor((hi - lo) / 2)

def find_magic_index(xs):
    lo, hi = 0, len(xs) - 1
    return do_find_magic_index(xs, 0, len(xs) - 1)

def do_find_magic_index(xs, lo, hi):
    pass

xss = [
    [],
    [-1,0,2,4,5,6],
    [1,1,1,1,1,5],
    [-2,-2,-2,-2,4],
    [1,2,3,4,5],
]

for xs in xss:
    print(xs)
    a = find_magic_index_brute(xs)
    b = find_magic_index(xs)
    print(a, b)
    assert a == b
    print("Success!")