binsearch.py

• 이전 버전 코드

# N minimum_valid_integer
# I {"version": "2.0", "import": ["bisect"], "abc": ["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
    return bisect.bisect_left(
        type('X', (), {'__getitem__': lambda self, x: is_valid(x)})(), True,
        beg, end - 1)

• 파라메트릭 서치와 bisect 모듈을 이용한 파라메트릭 서치 구현을 참고 

# N maximum_valid_integer
# I {"version": "2.0", "import": ["bisect"], "abc": ["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
    return bisect.bisect_right(
        type('X', (), {'__getitem__': lambda self, x: not is_valid(x)})(),
        False, beg, end - 1) - 1

• 파라메트릭 서치와 bisect 모듈을 이용한 파라메트릭 서치 구현을 참고