三分探索

概要

実関数 $f$ の $\arg \min_{x \in [l,r]} f(x)$ を求める．

計算量

200 回くらい回しておく．

使い方

$\arg \min_{x \in [l,r]} f(x)$ を求める．$f(x)$ は下に凸の実関数でないといけない

実装

template <class Function>
double ternarySearch(double l, double r, Function f) {
    for (int i = 0; i < 200; i++) {
        double a = (l + l + r) / 3;
        double b = (l + r + r) / 3;
        if (f(a) > f(b))
            l = a;
        else
            r = b;
    }
    return l;
}