Búsqueda ternaria
# Búsqueda ternaria

Un algoritmo de búsqueda ternaria es una técnica en ciencias de la computación para hallar los extremos de una función (máximo o mínimo) de una función unimodal. Una búsqueda ternaria determina que el extremo que se busca, no puede estar en el primer tercio del dominio o que no puede estar en el último tercio del dominio, luego se repite el proceso en los dos tercios restantes. Una búsqueda ternaria es un ejemplo de un Algoritmo divide y vencerás (ver Algoritmo de búsqueda).

## Función

Supongamos que estamos buscando un máximo de f(x) y sabemos que el máximo se encuentra en algún lugar entre A y B. Para que el algoritmo sea aplicable debe haber un valor x tal que

* para todo a,b con A ≤ a < b ≤ x, tenemos que f(a) < f(b), y
* para todo a,b con x ≤ a < b ≤ B, tenemos que f(a) > f(b).

## Algoritmo

Sea f(x) una función unimodal en el intervalo [l; r]. Tomamos dos puntos $m_1$ y $m_2$ en este segmento: l < $m_1$ < $m_2$ < r. Entonces, hay tres posibilidades:

* Si $f(m_1)$ < $f(m_2),$ entonces el máximo requerido no puede ubicarse en el lado izquierdo - [l; $m_1].$ Esto significa que el máximo debe buscarse en el intervalo $[m_1;r]$
* Si $f(m_1)$ > $f(m_2),$ de manera similar al anterior caso. Ahora, el máximo requerido no puede estar en el lado derecho - $[m_2;$ r], así que debe buscarse en el segmento [l; $m_2]$
* Si $f(m_1)$ = $f(m_2),$ entonces la búsqueda debe realizarse en $[m_1;$ $m_2],$ pero este caso se puede atribuir a cualquiera de los dos anteriores (para simplificar el código). Tarde o temprano, la longitud del segmento será un poco menor que una constante predeterminada, y el proceso podrá detenerse.

Puntos de partición $m_1$ y $m_2:$

* $m_1$ = l + (r-l)/3
* $m_2$ = r - (r-l)/3

### Tiempo de ejecución

    $T(n)=T(2n/3)+1=\Theta (\log n)$

### Algoritmo Recursivo

en lenguaje Python:

en lenguaje C:

### Algoritmo Iterativo

en lenguaje Python:

en lenguaje C:

