Búsqueda binaria sobre la respuesta
Hazle búsqueda binaria al espacio de RESPUESTAS, no a un array.
Optimización → decisión sí/no repetida.
El replanteo
- Difícil: "¿cuál es la suma más chica de la parte más grande al dividir en k?"
- Fácil: "¿podemos dividir en ≤ k partes, cada una ≤ L?" (verificación greedy)
- La verificación es MONÓTONA en L: una vez factible, se queda factible
- Así que las respuestas están ordenadas por factibilidad → búsqueda binaria al umbral
Míralo buscar en el espacio de respuestas
Divide [7,2,5,10,8] en 2. Límites candidatos 10..32; verde = factible, rojo = no.
Converge en 18: [7,2,5]=14, [10,8]=18.
Verificaciones logarítmicas vs lineales
Rango de ~2M: recorrer cada candidato = 228,000 verificaciones; búsqueda binaria = 20. Duplicar el rango agrega UNA verificación.
Requisitos + trampas
- El predicado debe ser MONÓTONO — demuéstralo, o converge en una babosada
- Encierra bien las cotas (extremo bajo inviable, extremo alto factible)
- Mínimo-factible vs máximo-factible necesitan reglas de actualización distintas (¡punto medio hacia arriba!)
- Respuesta de valor real → itera hasta una tolerancia
- Muchas veces es "búsqueda binaria envuelta alrededor de un greedy"
Para llevar
La búsqueda binaria solo necesita un predicado monótono — un array ordenado es apenas un caso.
"Optimizar" muchas veces se reduce a "decidir, repetidamente".
Siguiente bloque: estructuras avanzadas y probabilísticas.