binsearch.py

def binsearch(l, x):
    f, t = 0, len(l) - 1
    j = (f + t) // 2
    while f <= t:
        j = (f + t) // 2
        if l[j] == x:
            break
        elif l[j] < x:
            f = j + 1
        else:
            t = j - 1
    if l[j] < x:
        return l[:j+1], l[j+1:]
    else:
        return l[:j], l[j:]

if __name__ == '__main__':
    l = [1, 2, 4, 6, 7, 10, 12]
    for key, smaller, larger in [
        [4, [1, 2], [4, 6, 7, 10, 12]],
        [8, [1, 2, 4, 6, 7], [10, 12]]
    ]:
        l1, l2 = binsearch(l, key)
        assert (l1, l2) == (smaller, larger), f'{(l1, l2)}, {(smaller, larger)}'