src/Helper/TernarySearch.hpp

View this file on GitHub
Last update: 2020-04-18 20:15:36+09:00
Include: #include "src/Helper/TernarySearch.hpp"

概要

三分探索で整数を引数とする凸関数の極値を求める。 fの評価回数は、O(log (r - l))。

Verified with

test/yukicoder/1028.test.cpp

Code

/// @docs src/Helper/TernarySearch.md
template <class F, class T = long long> T ternary_search(T l, T r, F f, bool is_max = true) {
    auto g = [&f, &is_max](T x) { return is_max ? f(x) : -f(x); };
    while (std::abs(l - r) > 2) {
        T m1 = (2 * l + r) / 3, m2 = (l + 2 * r) / 3;
        if (g(m1) < g(m2))
            l = m1;
        else
            r = m2;
    }
    // 極値のindexは[l, r)の範囲で、abs(l - r) <= 2になっている
    if (l + 1 < r && g(l + 1) > g(l)) l = l + 1;
    return l;
}

#line 1 "src/Helper/TernarySearch.hpp"
/// @docs src/Helper/TernarySearch.md
template <class F, class T = long long> T ternary_search(T l, T r, F f, bool is_max = true) {
    auto g = [&f, &is_max](T x) { return is_max ? f(x) : -f(x); };
    while (std::abs(l - r) > 2) {
        T m1 = (2 * l + r) / 3, m2 = (l + 2 * r) / 3;
        if (g(m1) < g(m2))
            l = m1;
        else
            r = m2;
    }
    // 極値のindexは[l, r)の範囲で、abs(l - r) <= 2になっている
    if (l + 1 < r && g(l + 1) > g(l)) l = l + 1;
    return l;
}