bac_a_sable/dichotomy.py

import timeit

def first(iterable, validation):
    l, r = 0, len(iterable) - 1
    if validation(iterable[l]):
        return iterable[l]
    # if not validation(iterable[r]):
    #    return None
    while l < r:
        mid = (r + l) // 2
        if validation(iterable[mid]):
            r = mid
        else:
            l = mid + 1
    if not validation(iterable[l]):
        return None
    return iterable[r]

def last(iterable, validation):
    l, r = 0, len(iterable) - 1
    if validation(iterable[r]):
        return iterable[r]
    # if not validation(iterable[l]):
    #    return None
    while l < r:
        mid = (r + l) // 2
        if validation(iterable[mid]):
            l = mid + 1
        else:
            r = mid
    if not validation(iterable[r]):
        return None
    return iterable[r - 1]

lst = [0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0]
def test(i):
    return i == 4

print(first(lst, test))