Búsqueda ternaria

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).

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.

Puntos de partición m₁ y m₂:

• m₁ = l + (r-l)/3
• m₂ = r - (r-l)/3

Tiempo de ejecución

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

def BusquedaTernaria(f, l, r, absolutePrecision):
    '''
    l y r son los límites actuales; 
    el máximo está entre ellos;
    absolutePrecision es el nivel de precisión
    '''
    if abs(r - l) < absolutePrecision:
        return (l + r)/2

    m1 = (2*l + r)/3
    m2 = (l + 2*r)/3

    if f(m1) < f(m2):
        return BúsquedaTernaria(f, m1, r, absolutePrecision) 
    else:
        return BúsquedaTernaria(f, l, m2, absolutePrecision)

double BusquedaTernaria(double f[] ,int l ,int r ,double absolutePrecision )
{
    //l y r son los límites actuales; 
    //el máximo está entre ellos;
    //absolutePrecision es una constante predeterminada
 
	if(r-l <=  absolutePrecision)
	{
		return  ( l  +  r ) / 2.0;
	}
	else
	{
	    int m1  =  ( 2 * l  +  r ) / 3;
		int m2  =  ( l  +  2 * r ) / 3;

	    if(f[m1]< f[m2])
	    {
    	    return  BusquedaTernaria( f ,  m1 ,  r ,  absolutePrecision );
		}
    	else
	    {
			return  BusquedaTernaria ( f ,  l ,  m2 , absolutePrecision );
		}		
	}
}

def BusquedaTernaria(f, l, r, absolutePrecision):
    """
    Buscar el máximo de la función unimodal f () dentro de [l, r]
    Para encontrar el mínimo, invierta la instrucción if / else o invierta la comparación.
    """
    while True:
        #l and r son los límites actuales; el máximo está entre ellos
        if abs(r - l) < absolutePrecision:
            return (l + r)/2

        m1 = l + (r - l)/3
        m2 = r - (r - l)/3

        if f(m1) < f(m2):
            l = m1
        else:
            r = m2

double BusquedaTernaria(double f[] ,int l ,int r ,double absolutePrecision )
{
    //Buscar el máximo de la función unimodal f () dentro de [l, r] 
    //Para encontrar el mínimo, invierta la instrucción if / else o invierta la comparación. 
	bool b=true;
    while(b==true)
	{
        if( r - l  <=  absolutePrecision)
        {
        	b=false;
            return  ( l +  r) / 2;
		}
        int m1  =  ( 2 * l  +  r ) / 3;
		int m2  =  ( l  +  2 * r ) / 3;
		if(f[m1]< f[m2]) 
		{
        	l  =  m1;
		}
        else
        {
        	r  =  m2;
		}
	}    
}

• Búsqueda de la sección dorada
• Búsqueda binaria
• Búsqueda exponencial

• Esta obra contiene una traducción derivada de «Ternary search» de Wikipedia en inglés, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.