from typing import Callable


def binSearch(start: int, stop: int, check: Callable[[int], bool]) -> int:
    """
    Binary search algorithm in the interval (start, stop)

    Usage: binSearch(start, stop, check)

    Assuming that check(start) = True and check(stop) = False, performs binary search on the interval,
    returning the last value such that check(value) == True.
    This assumes that check is monotone, meaning that check(value) == True for value <= solution
    and check(value) == False for value > solution
    """
    interval = stop - start
    if interval == 1:
        return start
    middle = start + interval // 2
    checkMiddle = check(middle)
    if checkMiddle:
        return binSearch(middle, stop, check)
    else:
        return binSearch(start, middle, check)