Тернарный поиск

Бинарный поиск требует монотонности: слева от границы одно, справа другое. Но постоянно встречаются задачи, где функция сначала убывает, а потом растёт, — и нужен её минимум.

Такая функция называется унимодальной. Формально: существует точка $x^*$, левее которой функция строго убывает, а правее строго возрастает.

flowchart LR
    A["строго убывает"] --> B(("минимум x*"))
    B --> C["строго возрастает"]

Условие «строго» существенно. Если у функции есть плоский участок — например, она равна константе на целом отрезке, — тернарный поиск ломается: он не может определить, в какую сторону двигаться.

Идея

Возьмём две точки внутри отрезка, $m_1 < m_2$, и сравним значения.

Если $f(m_1) \le f(m_2)$, то минимум лежит левее $m_2$. Действительно: будь он правее, функция на участке от $m_1$ до $m_2$ ещё убывала бы, и было бы $f(m_1) > f(m_2)$. Значит, правую границу можно двинуть в $m_2$.

Симметрично при $f(m_1) > f(m_2)$ минимум правее $m_1$.

Каждый шаг отрезает треть отрезка. За $k$ шагов длина умножается на $(2/3)^k$ — тоже логарифм, только основание не 2, а 1.5.

Вещественный вариант

double ternary(double lo, double hi, function<double(double)> f) {
    for (int i = 0; i < 200; i++) {
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2)) hi = m2; else lo = m1;
    }
    return (lo + hi) / 2;
}

Число итераций считается так же, как в вещественном бинарном поиске, только основание другое: каждый шаг делит на $1.5$, а не на $2$. Чтобы сузить отрезок в $10^{15}$ раз, бинарному нужно $50$ шагов, тернарному — примерно $86$. Двести с запасом хватает почти всегда.

Обратите внимание: фиксированное число итераций, а не while (hi - lo > eps). Причина ровно та же, что и в бинарном поиске: при большом ответе разность границ может никогда не стать меньше эпсилона, и цикл зависнет.

И ещё: f вызывается дважды на каждой итерации. Если проверка стоит $O(n)$, общая сложность — $2 \cdot 200 \cdot n$. Это заметно дороже бинарного поиска, и на пределе по времени разница видна.

Целочисленный вариант

С целыми числами тернарный поиск неудобен: деление на три даёт округления, и на коротком отрезке легко потерять ответ. Надёжнее свести к трём элементам и добить перебором.

long long ternaryInt(long long lo, long long hi, function<long long(long long)> f) {
    while (hi - lo > 2) {
        long long m1 = lo + (hi - lo) / 3;
        long long m2 = hi - (hi - lo) / 3;
        if (f(m1) <= f(m2)) hi = m2; else lo = m1;
    }
    long long best = lo;
    for (long long x = lo; x <= hi; x++) if (f(x) < f(best)) best = x;
    return best;
}

Но есть способ проще.

Бинарный поиск вместо тернарного

Целочисленный минимум унимодальной функции ищется обычным бинарным поиском — по признаку «функция ещё убывает».

Предикат: $f(m) < f(m+1)$. Он ложен, пока функция убывает, и истинен с момента, где она начала расти. Ровно то, для чего бинарный поиск и предназначен.

long long argmin(long long lo, long long hi, function<long long(long long)> f) {
    while (hi - lo > 1) {
        long long m = lo + (hi - lo) / 2;
        if (f(m) < f(m + 1)) hi = m; else lo = m + 1;
    }
    return f(lo) <= f(hi) ? lo : hi;
}

Это лучше во всём: одно вычисление функции на шаг вместо двух, основание логарифма 2 вместо 1.5, нет возни с округлением. По сути, это бинарный поиск по дискретной производной.

Тот же приём работает и для вещественных: если производную можно выписать явно, бинарный поиск по её знаку точнее и вдвое дешевле тернарного.

Поэтому на практике тернарный поиск нужен реже, чем кажется. Он оправдан там, где функция вещественная, производную выписывать лень, а вычисление $f$ дёшево.

Классическая задача: путь через две среды

Из точки $(0, 1)$ надо попасть в точку $(1, 0)$. Прямая $y = a$ делит квадрат на две зоны: сверху поле со скоростью $v_p$, снизу лес со скоростью $v_f$.

Идти по прямой невыгодно: если по полю бежится втрое быстрее, разумно дать крюк, чтобы больше пути пройти по полю.

Пусть граница пересекается в точке с абсциссой $x$. Тогда

$$T(x) = \frac{\sqrt{x^2 + (1-a)^2}}{v_p} + \frac{\sqrt{(1-x)^2 + a^2}}{v_f}$$

Каждое слагаемое выпукло, сумма выпуклых выпукла, значит функция унимодальна — тернарный поиск применим. Границы: $x$ от $0$ до $1$, потому что выходить за квадрат заведомо невыгодно.

Проверить унимодальность стоит до написания кода. Самая частая ошибка на таких задачах — навесить тернарный поиск на функцию с двумя локальными минимумами и получить не тот ответ на закрытых тестах.

Вторая классика: велогонка

Гонщики стартуют из точек $x_i$ и едут со скоростями $v_i$. В момент $t$ каждый находится в $x_i + v_i t$. Нужен момент, когда расстояние между самым передним и самым задним минимально:

$$g(t) = \max_i (x_i + v_i t) - \min_i (x_i + v_i t)$$

Здесь унимодальность видна из общего факта: максимум линейных функций выпуклый, минимум линейных вогнутый, а разность выпуклой и вогнутой выпукла. Значит, тернарный поиск применим, причём это доказано, а не «видно из картинки».

Проверка стоит $O(n)$ — один проход по гонщикам. Итог: $O(n \log)$ с константой 2 из-за двух вызовов на шаг.

Когда унимодальности нет

Если функция имеет несколько локальных минимумов, ни тернарный, ни бинарный поиск не помогут. Варианты:

• разбить область на участки, где унимодальность есть, и обработать каждый;
• пройтись грубой сеткой, найти окрестность лучшего значения и уже там запустить тернарный поиск;
• поискать другую формулировку задачи — часто «неунимодальная» функция становится унимодальной после замены переменной.

Проверять унимодальность удобно стрессом: сгенерировать случайные входные данные, посчитать функцию в тысяче точек и убедиться, что знак разности меняется ровно один раз.