from typing import Callable
from typing import Optional


def bisect_index(
        check: Callable[[int], bool],
        known_f: int = 0,
        known_t: Optional[int] = None) -> int:

    """Finds the first index for which a function changes from False to True.

    check: A boolean function over integers in the range [known_f, known_t], or
        all integers >= known_f if known_t is None. In this range, there must
        be some integer i such that check(j) == (j >= i) for all j in the range

    known_f: An index for which check is known to return False. Determines the
        lower bound of the search

    known_t: An index for which check is known to return True. If known_t is
        None, the search will be conducted forward from known_f without bound
    """

    # if only a False index is known, search for a True index
    if known_t is None:
        step_size = 1
        i = known_f + 1
        while not check(i):
            # search forward with increasingly large step size
            step_size *= 2
            i += step_size
        known_t = i

    # binary search over indices to find first True index
    while known_f < known_t - 1:
        mid = (known_f + known_t) // 2
        if not check(mid):
            known_f = mid
        else:
            known_t = mid

    return known_t