Тернарный ПоискTernary Search

Поддерживается диапазон [lo, hi], про который известно: экстремум (например, максимум) функции f лежит внутри него. Внутри диапазона выбираются две точки m1 = lo + (hi-lo)/3 и m2 = hi - (hi-lo)/3, делящие его на три равные части. Если f(m1) < f(m2), то максимум не может лежать левее m1 (функция там либо ещё растёт к m1, либо уже убывает и на отрезке [lo, m1] заведомо ниже, чем в окрестности m2) — значит lo можно сдвинуть до m1. Симметрично, если f(m1) ≥ f(m2), максимум не может быть правее m2, и hi сдвигается до m2. В любом случае отбрасывается ровно треть диапазона, а не половина — отсюда чуть больший, но всё ещё логарифмический, коэффициент по сравнению с бинарным поиском.A range [lo, hi] is maintained, about which it's known: f's extremum (say, a maximum) lies inside it. Inside the range, two points m1 = lo + (hi-lo)/3 and m2 = hi - (hi-lo)/3 are chosen, splitting it into three equal parts. If f(m1) < f(m2), the maximum can't lie to the left of m1 (the function there is either still rising toward m1, or already falling and provably lower on [lo, m1] than near m2) — so lo can move to m1. Symmetrically, if f(m1) ≥ f(m2), the maximum can't be to the right of m2, and hi moves to m2. Either way exactly one third of the range is discarded, not half — hence a slightly larger, but still logarithmic, constant compared to binary search.

double ternary_search_max(std::function<double(double)> f, double lo, double hi, int iters) {
    for (int i = 0; i < iters; ++i) {
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2)) lo = m1;  // максимум не левее m1// max is not left of m1
        else hi = m2;             // максимум не правее m2// max is not right of m2
    }
    return (lo + hi) / 2;
}

График — перевёрнутая парабола с настраиваемым положением пика. Оранжевые точки — m1 и m2 на текущем шаге, синяя область — оставшийся диапазон [lo, hi], красная (полу)область — то, что было отброшено на этом шаге.The graph is an inverted parabola with a configurable peak position. The orange dots are m1 and m2 at the current step, the blue region is the remaining range [lo, hi], the red (semi-)region is what got discarded on this step.

Заманчиво предположить, что деление на три части даёт лучшую асимптотику, чем деление пополам — но нет: тернарный поиск на каждом шаге вычисляет f дважды (в m1 и m2), тогда как бинарный поиск для той же задачи (найти экстремум через сравнение производной с нулём, если она доступна) вычисляет предикат один раз. Число шагов для сужения диапазона в K раз — log₁.₅(K) для тернарного поиска против log₂(K) для честного деления пополам с одним вычислением — а log₁.₅(K) > log₂(K), да ещё с двойной стоимостью каждого шага. Тернарный поиск оправдан ровно тогда, когда нет доступа к производной или сравнению "растёт/убывает" дешевле, чем через два вызова f — то есть когда сама природа задачи не даёт более дешёвого предиката.It's tempting to assume splitting into three parts gives better asymptotics than splitting in half — but no: ternary search evaluates f twice per step (at m1 and m2), whereas binary search for the same problem (finding an extremum via comparing the derivative to zero, if available) evaluates a predicate once. The number of steps to shrink the range by a factor of K is log₁.₅(K) for ternary search versus log₂(K) for honest halving with a single evaluation — and log₁.₅(K) > log₂(K), with double the per-step cost on top. Ternary search is justified exactly when there's no access to the derivative or a cheaper "rising/falling" comparison than two calls to f — i.e. when the problem's own nature offers no cheaper predicate.