めぐる式二分探索 (lib/algorithm/binary_search.hpp)

• View this file on GitHub
• Last update: 2026-03-24 01:55:57+09:00
• Include: #include "lib/algorithm/binary_search.hpp"

Verified with

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

Code

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

/// @brief めぐる式二分探索
template <class T, class F>
T meguru_binary_search(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;
}

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

/// @brief めぐる式二分探索
template <class T, class F>
T meguru_binary_search(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;
}

Back to top page