Búsqueda ternaria

Tema: Búsqueda Binaria · temarios: Syllabus OCI · Syllabus IOI

📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.

Qué hace

Encuentra el mínimo (o el máximo) de una función unimodal, que baja hasta un punto y después sube, descartando un tercio del rango en cada paso.

Complejidad: O(log(rango) · costo de evaluar la función). Sobre enteros, la versión de abajo hace una sola evaluación por paso en vez de dos.

Cuándo usarlo

Cuando te piden minimizar algo que no es monótono sino con forma de valle: primero mejora y después empeora. Típico en geometría (distancia a una recta), en repartos equilibrados y al elegir un parámetro cuyo costo tiene un óptimo interior.

Implementación recomendada (C++)

// f la escribes tú: el costo que quieres minimizar. El contrato es exigente:
// ESTRICTAMENTE decreciente hasta el mínimo y ESTRICTAMENTE creciente después.
// (Un fondo plano sí está permitido; una meseta en la ladera, no — ver Notas.)
long long f(long long x);
 
// ENTEROS — la versión que conviene usar: compara vecinos y hace binaria sobre
// la pendiente. Evalúa f dos veces por paso, igual que la ternaria clásica,
// pero parte el rango por la MITAD en vez de descartar solo un tercio.
// (Un fondo plano no la molesta; una meseta en la LADERA sí — ver Notas.)
long long argmin_entero(long long lo, long long hi) {
    while (lo < hi) {
        long long m = lo + (hi - lo) / 2;
        if (f(m) < f(m + 1)) hi = m;      // ya va subiendo: el mínimo está en [lo, m]
        else                 lo = m + 1;  // sigue bajando (o empata): está en [m+1, hi]
    }
    return lo;                            // lo == hi == la posición del mínimo
}
 
// REALES — la ternaria de verdad: dos cortes que dejan tres tercios.
double g(double x);
 
double argmin_real(double lo, double hi) {
    for (int it = 0; it < 200; it++) {           // 200 vueltas: (2/3)^200, de sobra
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        if (g(m1) < g(m2)) hi = m2;              // el mínimo no está pasado m2
        else               lo = m1;              // ni antes de m1
    }
    return lo;
}

⚠️ Notas

⚠️ La trampa al pasar la ternaria a enteros: si traduces el ciclo de reales tal cual —while (lo < hi) con los dos tercios— se cuelga. Cuando queda hi - lo == 1, los cortes dan m1 == lo y m2 == hi, así que ambas ramas dejan el rango igual y el ciclo gira para siempre (probado: falla en el 100% de los casos). La ternaria clásica sí sirve sobre enteros, pero solo si le pones la guarda while (hi - lo > 2) y después revisas a mano las 3 posiciones que quedan. La versión de vecinos de arriba se ahorra ese cuidado y además evalúa f una vez por paso en vez de dos, que es la mitad del trabajo cuando evaluar es caro. ⚠️ Mesetas en la ladera: no hay método logarítmico que sobreviva. Con f = [5, 5, 3, 3, 7, 7] la búsqueda de vecinos devuelve 7 en vez de 3, y no es un bug arreglable: si la función puede tener tramos planos fuera del fondo, el mínimo se puede esconder en cualquier parte del tramo y hay que mirarlos todos, O(n). Por eso el contrato pide laderas estrictas. Un fondo plano, en cambio, no molesta: ahí la versión entera devuelve una de las posiciones que alcanzan el mínimo. En reales, corta por número de iteraciones, no por hi - lo > eps: con rangos grandes el epsilon absoluto puede no alcanzarse nunca por la precisión del double. Para maximizar, invierte las comparaciones (o minimiza -f). 📋 Estatus: ni el Syllabus IOI ni el Syllabus OCI nombran la búsqueda ternaria; lo que sí piden explícitamente es la Búsqueda binaria sobre la respuesta. Tenla como herramienta ad-hoc para cuando la función tenga forma de valle, no como tema de estudio prioritario.

🔗 Relacionados