algorithm.py

from typing import Callable, Tuple

def calc_range(f: Callable[[int], bool], start: int = 1, max_steps: int = 64) -> Tuple[int, int]:
    """
    通过指数扩张查找单调谓词f的区间边界，返回(min_value, max_value)，满足：
    - f(min_value) == True
    - f(max_value) == False

    要求f在整数域上呈现True到False的单调变化（形如TTT...FFF...）。
    """
    num = start
    prev = 0
    for _ in range(max_steps):
        if f(num):
            prev = num
            num *= 2
        else:
            return prev, num
    raise RuntimeError("calc_range: 未在限幅内找到上界，请检查f的单调性或增大max_steps")


def binary_search(f: Callable[[int], bool], min_value: int, max_value: int) -> int:
    """
    在给定区间[min_value, max_value]且满足f(min)=True、f(max)=False的前提下，
    返回最小使f为False的整数（即单调变化的拐点）。
    """
    while min_value < max_value - 1:
        mid = (min_value + max_value) // 2
        if f(mid):
            min_value = mid
        else:
            max_value = mid
    return max_value


def search_with_upper(f: Callable[[int], bool], upper: int) -> int:
    """当已知上界upper时，在[0, upper]直接二分搜索拐点。"""
    return binary_search(f, 0, upper)


__all__ = ["calc_range", "binary_search", "search_with_upper"]