utility/binary_search.cpp

• View this file on GitHub
• Last update: 2021-12-17 09:20:39+09:00

Code

#pragma once
#include <cassert>
#include <type_traits>

template <class T, class F, std::enable_if_t<std::is_integral_v<T>>* = nullptr>
T binary_search(T ok, T ng, const F& f) {
    using U = std::make_unsigned_t<T>;
    assert(ok != ng);
    if (ok < ng) {
        while (ok + 1 != ng) {
            const T md = ok + T((U(ng) - U(ok)) >> 1);
            (f(md) ? ok : ng) = md;
        }
    } else {
        while (ng + 1 != ok) {
            const T md = ng + T((U(ok) - U(ng)) >> 1);
            (f(md) ? ok : ng) = md;
        }
    }
    return ok;
}

#line 2 "utility/binary_search.cpp"
#include <cassert>
#include <type_traits>

template <class T, class F, std::enable_if_t<std::is_integral_v<T>>* = nullptr>
T binary_search(T ok, T ng, const F& f) {
    using U = std::make_unsigned_t<T>;
    assert(ok != ng);
    if (ok < ng) {
        while (ok + 1 != ng) {
            const T md = ok + T((U(ng) - U(ok)) >> 1);
            (f(md) ? ok : ng) = md;
        }
    } else {
        while (ng + 1 != ok) {
            const T md = ng + T((U(ok) - U(ng)) >> 1);
            (f(md) ? ok : ng) = md;
        }
    }
    return ok;
}

Back to top page