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

Троичный поиск (или тернарный поиск) — метод поиска минимума или максимума функции на отрезке.

Алгоритм

Рассмотрим этот алгоритм на примере поиска минимума (поиск максимума аналогичен).

Пример

Пусть функция [math]f(x)[/math] на отрезке [math][l, r][/math] имеет минимум, и мы хотим найти точку [math]x_{min}[/math], в которой он достигается.

Посчитаем значения функции в точках [math] a = l + \frac{(r-l)}{3} [/math] и [math] b = l + \frac{2(r-l)}{3} [/math].

Так как в точке [math]x_{min}[/math] минимум, то на отрезке [math][l, x_{min}][/math] функция — выпуклая вниз.

[math] \forall x', x'' \in [l, r]: \\ l \lt x' \lt x'' \lt x_{min} \Rightarrow f(l) \gt f(x') \gt f(x'') \gt f(x_{min}) \\ x_{min} \lt x' \lt x'' \lt r \Rightarrow f(x_{min}) \lt f(x') \lt f(x'') \lt f(r) [/math].

Значит если [math]f(a) \lt f(b)[/math], то [math]x_{min} \in [l, b][/math], аналогично из [math]f(a) \gt f(b)[/math] следует [math] x_{min} \in [a, r][/math]. Тогда нам нужно изменить границы поиска и искать дальше, пока не будет достигнута необходимая точность, то есть [math] r-l \lt \varepsilon [/math].

Псевдокод

ternarySearchMin(f, l, r, eps) 
  if (r - l < eps)
    return (left + right) / 2
  a = (left * 2 + right) / 3
  b = (left + right * 2) / 3
  if (f(a) < f(b))
    return ternarySearch(f, l, b, eps)
  else
    return ternarySearch(f, a, r, eps)
end

Возможен и нерекурсивный вариант:

ternarySearchMin(f, l, r, eps) 
  while (r - l < eps) 
  {
    a = (left * 2 + right) / 3
    b = (left + right * 2) / 3
    if (f(a) < f(b))
      r = b
    else
      l = a
  }
  return (left + right) / 2
end

Время работы

Так как на каждой итерации мы считаем два значения функции и уменьшаем область поиска в полтора раза, пока [math] r - l \gt \varepsilon[/math], то время работы алгоритма составит [math]2 \log_{\frac32} \left(\frac{r - l}{\varepsilon}\right)[/math]

Смотрите также

Есть оптимизация этого алгоритма, если делить отрезок не на равные части, а в отношении золотого сечения, — Поиск с помощью золотого сечения

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

Литература

Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching.