libs/binary_search.py

• View this file on GitHub
• Last update: 2025-09-11 18:15:20+09:00

Code

from typing.abc import Callable


def binary_search(
    fn: Callable[[int], bool],
    right: int = 0,
    left: int = -1,
    return_left: bool = True,
) -> int:
    """二分探索の抽象的なライブラリ

    評価関数の結果に応じて、二分探索する
    最終的にはleftを出力します

    関数のテンプレート
    def check(mid:int):
        if A[mid] > x:
            return True
        else:
            return False

    midは必須です。それ以外はご自由にどうぞ
    """
    while right - left > 1:
        mid = (left + right) // 2

        if fn(mid):
            left = mid
        else:
            right = mid

    return left if return_left else right

Back to top page