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₁ y m₂ en este segmento: l < m₁ < m₂ < r. Entonces, hay tres posibilidades:

Si f(m₁) < f(m₂), entonces el máximo requerido no puede ubicarse en el lado izquierdo - [l; m₁]. Esto significa que el máximo debe buscarse en el intervalo [m₁;r]
Si f(m₁) > f(m₂), de manera similar al anterior caso. Ahora, el máximo requerido no puede estar en el lado derecho - [m₂; r], así que debe buscarse en el segmento [l; m₂]
Si f(m₁) = f(m₂), entonces la búsqueda debe realizarse en [m₁; m₂], 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.