Троичный поиск

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Функция[править | править вики-текст]

Предположим, что мы ищем максимум функции 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).

Алгоритм[править | править вики-текст]

double l = ..., r = ..., EPS = ...; // входные данные
while (r - l > EPS) {
   double m1 = l + (r - l) / 3,
      m2 = r - (r - l) / 3;
   if (f (m1) < f (m2))
      l = m1;
   else
      r = m2;
}

См. также[править | править вики-текст]