検証済み · 最終更新 2026-09-07 · GitHub

境界を求める二分探索

lib/algorithm/binary_search.hpp

インクルード

#include "algorithm/binary_search.hpp"

関数

名前	説明
`binary_search_boundary`	境界を求める二分探索

検証

検証プログラム（3）

test/aoj/challenge/2270.test.cpp test/aoj/challenge/2270.test.cpp
test/aoj/course/ALDS1_14_D.test.cpp test/aoj/course/ALDS1_14_D.test.cpp
test/yosupo/math/kth_root_integer.test.cpp test/yosupo/math/kth_root_integer.test.cpp

実装

#pragma once
#include <cmath>
#include <cstdint>
#include <numeric>

/// @brief 境界を求める二分探索
/// @param ok 条件を満たすことが既知の初期値
/// @param ng 条件を満たさないことが既知の初期値
/// @param check 単調な判定関数
/// @return 条件を満たす境界側の値
/// @complexity 初期間隔を $D=|ok-ng|$ として $O(\log D)$ 回の判定
template <class T, class F>
T binary_search_boundary(T ok, T ng, F check) {
    while (std::abs(ok - ng) > 1) {
        T mid = std::midpoint(ok, ng);
        (check(mid) ? ok : ng) = mid;
    }
    return ok;
}

bundled

#line 2 "lib/algorithm/binary_search.hpp"
#include <cmath>
#include <cstdint>
#include <numeric>

/// @brief 境界を求める二分探索
/// @param ok 条件を満たすことが既知の初期値
/// @param ng 条件を満たさないことが既知の初期値
/// @param check 単調な判定関数
/// @return 条件を満たす境界側の値
/// @complexity 初期間隔を $D=|ok-ng|$ として $O(\log D)$ 回の判定
template <class T, class F>
T binary_search_boundary(T ok, T ng, F check) {
    while (std::abs(ok - ng) > 1) {
        T mid = std::midpoint(ok, ng);
        (check(mid) ? ok : ng) = mid;
    }
    return ok;
}