목차

(old) binsearch.py

minimum_valid_integer v1.0

코드

# N minimum_valid_integer
# I {"version": "1.0", "typing": ["Callable"]}
def minimum_valid_integer(beg: int, end: int, is_valid: Callable[[int],
                                                                 bool]) -> int:
    ''' Returns the minimum int X in [beg, end) where is_valid(X) is true. '''
    if not is_valid(end - 1):
        raise ValueError
    while beg + 1 < end:
        mid = (beg + end - 1) >> 1
        if is_valid(mid):
            end = mid + 1
        else:
            beg = mid + 1
    return beg

maximum_valid_integer v1.0

코드

# N maximum_valid_integer
# I {"version": "1.0", "typing": ["Callable"]}
def maximum_valid_integer(beg: int, end: int, is_valid: Callable[[int],
                                                                 bool]) -> int:
    ''' Returns the maximum int X in [beg, end) where is_valid(X) is true. '''
    if not is_valid(beg):
        raise ValueError
    while beg + 1 < end:
        mid = (beg + end) >> 1
        if is_valid(mid):
            beg = mid
        else:
            end = mid
    return beg