Búsqueda binaria sobre la respuesta
Tema: Búsqueda Binaria · temarios: Syllabus OCI · Syllabus IOI
📍 Dónde se aprende: módulo 12 de la Ruta de Aprendizaje.
Qué problema resuelve
A veces es difícil encontrar directamente el mejor valor, pero resulta más sencillo comprobar uno propuesto. Por ejemplo: «¿cuál es la menor capacidad que permite guardar 23 unidades en 4 cajas iguales?» se transforma en «con capacidad x por caja, ¿alcanza el espacio?».
Esta ficha supone que ya puedes escribir esa comprobación. Si buscas un elemento en un arreglo ordenado, comienza por Búsqueda binaria clásica. Aquí ordenamos respuestas candidatas, no necesariamente elementos de un arreglo.
La condición que permite descartar la mitad
En el ejemplo, ok(x) significa 4*x >= 23. Al aumentar la capacidad, algo que ya era posible sigue siéndolo:
Capacidad x | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|
| ¿Alcanza? | no | no | no | sí | sí | sí |
Buscamos el primer verdadero, 6. Si probamos 5 y falla, ninguna capacidad menor sirve. Si probamos 7 y funciona, la respuesta puede ser 7 o algo menor. Esas implicaciones justifican cada descarte.
Para maximizar se necesita la dirección contraria. Si tenemos 23 unidades de cuerda y queremos piezas de 4 unidades, ok(x) significa «puedo obtener al menos x piezas», es decir, 4*x <= 23. La secuencia es sí…sí, no…no y buscamos el último verdadero, 5.
No intercambies las funciones manteniendo el mismo predicado: cada una exige una dirección de monotonía diferente. Si el predicado alterna entre verdadero y falso, estas plantillas no se aplican.
Contrato y resultado cuando no hay solución
Las funciones reciben un intervalo inclusivo con 0 <= lo <= hi <= LLONG_MAX y una función ok que devuelve siempre la misma respuesta para el mismo valor. Devuelven -1 si ningún candidato del intervalo sirve. Restringir los candidatos a números no negativos permite usar ese indicador sin confundirlo con una respuesta válida.
primer_okexigefalse…true. Comprobarok(hi)permite detectar que todo el intervalo falla.ultimo_okexigetrue…false. Comprobarok(lo)cumple el mismo propósito.- Si todos sirven, la primera devuelve
loy la segundahi.
La resta hi-lo cabe bajo este contrato. El punto medio superior se calcula sin sumar 1 a esa diferencia, que podría ser LLONG_MAX. El código de tu predicado también debe evitar desbordamientos: proteger el punto medio no protege expresiones como 4*x.
Implementación recomendada (C++)
// Contrato común: 0 <= lo <= hi <= LLONG_MAX; ok es un predicado puro.
// Devuelven -1 si no existe un valor factible en el intervalo.
// Minimizar: ok debe tener forma false...false,true...true.
template<class Predicado>
long long primer_ok(long long lo, long long hi, Predicado ok) {
if (!ok(hi)) return -1;
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
if (ok(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
// Maximizar: ok debe tener forma true...true,false...false.
template<class Predicado>
long long ultimo_ok(long long lo, long long hi, Predicado ok) {
if (!ok(lo)) return -1;
while (lo < hi) {
long long diferencia = hi - lo;
long long mid = lo + diferencia / 2 + diferencia % 2;
if (ok(mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}El parámetro de plantilla permite pasar una función o una lambda, por ejemplo primer_ok(0, 23, [](long long x) { return 4*x >= 23; }) devuelve 6. En ese intervalo el producto es seguro. ultimo_ok(0, 23, [](long long x) { return 4*x <= 23; }) devuelve 5.
En la primera función, el medio inferior hace que mid+1 avance cuando quedan dos candidatos. En la segunda, el medio superior permite que lo=mid avance en ese mismo caso. Usar el medio inferior en ambas puede producir un bucle infinito.
Costo: O(log(hi-lo+1)) comprobaciones, más la comprobación inicial del extremo. Multiplica por el costo de ok; la búsqueda no vuelve constante una verificación que recorre todo un arreglo.
Para comprobar que entendiste
Con 31 unidades y 6 cajas iguales, escribe primero una tabla de factibilidad para capacidades entre 3 y 7. Luego busca la mínima capacidad y prueba también el intervalo [0,4].
Comprobación
La capacidad mínima es 6. En
[0,4]no hay solución yprimer_okdevuelve-1. Antes de programar, explica por qué aumentar la capacidad nunca empeora la factibilidad.