Binary search
(byslib/utility/binary_search.py)

• View this file on GitHub
• Last update: 2022-04-18 22:29:22+09:00
• Link: https://twitter.com/meguru_comp/status/697008509376835584

Code

# @title Binary search
from typing import Callable


def meguru_bisect(ok: int, ng: int, is_ok: Callable[..., bool], *args) -> int:
    """Binary Search

    Parameters
    ----------
    ok
        Inital value s.t. is_ok(ok) == True
    ng
        Inital value s.t. is_ok(ng) == False
    is_ok
        Judge function

    Returns
    -------
        number of is_ok(x) == True and is_ok(x ± 1) == False

    Notes
    -----
    Time complexity

    O(log(abs(ok-ng)))

    References
    ----------
    ..[1] https://twitter.com/meguru_comp/status/697008509376835584

    Examples
    --------
    """
    assert is_ok(ok, *args)
    assert not is_ok(ng, *args)

    while abs(ok - ng) > 1:
        mid = (ok + ng) >> 1
        if is_ok(mid, *args):
            ok = mid
        else:
            ng = mid
    return ok

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.10.4/x64/lib/python3.10/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir], 'release': True}).decode()
  File "/opt/hostedtoolcache/Python/3.10.4/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/python.py", line 80, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page