algorithm/Others/binary_search.hpp

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Include: #include "algorithm/Others/binary_search.hpp"

Verified with

• verify/aoj-ALDS1_4_B-binary_search.test.cpp

Code

#ifndef ALGORITHM_BINARY_SEARCH_HPP
#define ALGORITHM_BINARY_SEARCH_HPP 1

#include <cassert>
#include <concepts>
#include <numeric>
#include <type_traits>

namespace algorithm {

template <std::integral Type, class Pred>
constexpr Type bisearch(Type ok, Type ng, Pred pred) {
    static_assert(std::is_invocable_r<bool, Pred, Type>::value);
    assert(ok <= ng);
    if(!pred(ok)) return ok;
    while(ng - ok > 1) {
        Type mid = std::midpoint(ok, ng);
        (pred(mid) ? ok : ng) = mid;
    }
    return ng;
}

template <std::floating_point Type, class Pred>
constexpr Type bisearch(Type ok, Type ng, Type eps, Pred pred) {
    static_assert(std::is_invocable_r<bool, Pred, Type>::value);
    assert(ok <= ng);
    if(!pred(ok)) return ok;
    while(ng - ok > eps) {
        Type mid = std::midpoint(ok, ng);
        (pred(mid) ? ok : ng) = mid;
    }
    return ng;
}

}  // namespace algorithm

#endif

#line 1 "algorithm/Others/binary_search.hpp"



#include <cassert>
#include <concepts>
#include <numeric>
#include <type_traits>

namespace algorithm {

template <std::integral Type, class Pred>
constexpr Type bisearch(Type ok, Type ng, Pred pred) {
    static_assert(std::is_invocable_r<bool, Pred, Type>::value);
    assert(ok <= ng);
    if(!pred(ok)) return ok;
    while(ng - ok > 1) {
        Type mid = std::midpoint(ok, ng);
        (pred(mid) ? ok : ng) = mid;
    }
    return ng;
}

template <std::floating_point Type, class Pred>
constexpr Type bisearch(Type ok, Type ng, Type eps, Pred pred) {
    static_assert(std::is_invocable_r<bool, Pred, Type>::value);
    assert(ok <= ng);
    if(!pred(ok)) return ok;
    while(ng - ok > eps) {
        Type mid = std::midpoint(ok, ng);
        (pred(mid) ? ok : ng) = mid;
    }
    return ng;
}

}  // namespace algorithm

Back to top page