Тернарный поиск: как найти минимум унимодальной функции и где грабли с целыми числами?
Есть функция, которая сначала убывает, потом возрастает (унимодальная), нужно найти её минимум. Слышал про тернарный поиск, но не понимаю, как он устроен и почему именно три точки. И как быть, если аргумент целочисленный — мой цикл while (l < r) зависает.
2 ответа
Тернарный поиск ищет экстремум унимодальной функции (строго убывает до точки минимума, потом строго возрастает). Идея: берём две внутренние точки m1 < m2, делящие отрезок на три части. Если f(m1) < f(m2), минимум не может быть правее m2 → отбрасываем (m2, r]. Иначе отбрасываем [l, m1). За одну итерацию отрезок сжимается в ~3/2 раза → O(log) итераций.
Вещественный вариант — по числу итераций (как и вещ. бинпоиск):
double l = L, r = R;
for (int it = 0; it < 200; it++) {
double m1 = l + (r - l) / 3;
double m2 = r - (r - l) / 3;
if (f(m1) < f(m2)) r = m2;
else l = m1;
}
// минимум ~ f((l + r) / 2)
Целочисленный вариант требует аккуратности, иначе зависание. Сужай, пока r - l >= 3, потом перебери оставшиеся точки:
int l = L, r = R;
while (r - l >= 3) {
int m1 = l + (r - l) / 3;
int m2 = r - (r - l) / 3;
if (f(m1) < f(m2)) r = m2;
else l = m1;
}
long long best = LLONG_MAX;
for (int x = l; x <= r; x++) best = min(best, f(x));
Сложность O(log(R-L) * cost(f)). Грабля с зависанием — именно от того, что при малом интервале m1 и m2 совпадают и отрезок не сжимается; «добивание» перебором этого 3-4 точек снимает проблему.
Важное предупреждение: тернарный поиск корректен только для строго унимодальной функции. Если есть плато (f(m1) == f(m2) на участке равных значений), наивное сравнение < может отбросить кусок, где лежит ответ. Для целых с возможными плато безопаснее свести к бинпоиску по разности f(x+1) - f(x): эта разность монотонно меняет знак с минуса на плюс в точке минимума, ищи бинпоиском первую позицию, где f(x+1) >= f(x). Это устойчивее и часто проще отлаживается.