Трои́чный по́иск (Тернарный поиск) — это метод в информатике для поиска максимумов и минимумов функции , которая либо сначала строго возрастает , затем строго убывает , либо наоборот. Троичный поиск определяет, что минимум или максимум не может лежать либо в первой, либо в последней трети области, и затем повторяет поиск на оставшихся двух третях. Троичный поиск демонстрирует парадигму программирования « разделяй и властвуй ».

Функция

Предположим, что мы ищем максимум функции f ( x ), и что нам известно, что максимум лежит между A и B . Чтобы алгоритм был применим, должно существовать некоторое значение x , такое, что

• для всех a , b , для которых A ≤ a < b ≤ x , выполняется f(a) < f(b) , и
• для всех a , b , для которых x ≤ a < b ≤ B , выполняется f(a) > f(b) .

Алгоритм

/**
Находит максимум функции с одним экстремумом между l и r.
Чтобы найти минимум - достаточно поменять местами действия в ветках if/else.
*/
double l = ..., r = ..., EPS = ...; // входные данные
double m1, m2;
while (r - l > EPS) {
   m1 = l + (r - l) / 3; 
   m2 = r - (r - l) / 3;
   if (f (m1) < f (m2))
      l = m1;
   else
      r = m2;
}

См. также

• Двоичный поиск (используется для поиска точки, где производная меняет знак)
• Метод Ньютона (используется для поиска точки, где производная обращается в ноль)
• Метод золотого сечения (схож с троичным поиском, полезен, если за одну итерацию вычисление f занимает больше всего времени)
• Интерполирующий поиск
• Линейный поиск