Búsqueda Binaria
Búsqueda binaria sobre la respuesta o estructuras.
Volver a los 11 temas · Referencia · temarios: Syllabus OCI · Syllabus IOI.
📍 Clases relacionadas: módulos 08 · 12 de la Ruta de Aprendizaje.
📋 En el temario OCI: desde la Regional (⊖): en secuencias ordenadas y sobre funciones monótonas.
Partir el espacio de búsqueda por la mitad, una y otra vez. Sirve para buscar en algo ordenado y —el salto grande del tema— para encontrar la mejor respuesta posible cuando «se puede con x» es monótono.
📌 Qué abarca
- Búsqueda binaria en un arreglo ordenado.
- Búsqueda binaria sobre la respuesta (parametric search): un predicado monótono convierte “optimizar” en “decidir factibilidad”.
- “Descenso” / búsqueda binaria sobre estructuras (p.ej. caminar un Fenwick o segment tree). Ver Estructuras de Datos.
⛔ Fuera del syllabus IOI
- Sin exclusiones propias. La pregunta que sí aparece: la búsqueda ternaria (para funciones unimodales, no monótonas) no está en el syllabus, aunque la optimización numérica multivariada sí está explícitamente fuera.
🎯 En competencia
En la OCI — Desde la Regional, en su versión avanzada: buscar en un arreglo ordenado y, sobre todo, sobre funciones monótonas (“¿cuál es el mínimo X tal que…?”). Es la técnica que más rendimiento da por lo poco que cuesta aprenderla. En este vault hay 8 problemas OCI del tema (3 de fases regionales, 4 de fases nacionales y 1 de clasificatorias IOI); están en la tabla de abajo.
En la IOI — “Binary search the answer” es de los trucos más rentables: transforma muchos problemas de optimización en uno de verificación, y suele dar subtareas completas.
⚠️ La trampa típica
El trío clásico: (lo+hi)/2 se desborda (usa lo + (hi-lo)/2), olvidar el ±1 al mover los extremos deja un ciclo infinito, y sobre reales no se compara con ==: se fija un número de iteraciones (~100).
⚙️ Algoritmos y técnicas
🇨🇱 Problemas OCI (en español)
Empieza por acá: son problemas oficiales chilenos, con enunciado en español y mirror para enviar. Consulta la orientación de estudio al comienzo de esta página. La dificultad orienta la elección, pero no garantiza una solución completa.
| Problema | Competencia | Dificultad |
|---|---|---|
| Bicicleta | 2016 Nacional | 🟢 fácil |
| Paltas | 2023 Regional | 🟡 media |
| Teletransportador cuántico de flujos | 2017 Clasificatoria | 🟡 media |
| La leyenda de Zolda | 2017 Nacional | 🟡 media |
| Reloj inteligente | 2018 Regional | 🟡 media |
| Cine | 2024 Nacional | 🟡 media |
| La leyenda de Zolda | 2017 Regional | 🔴 difícil |
| Catalonia | 2020 Nacional | 🔴 difícil |
🌍 Problemas IOI
De más abordable a más duro, según el puntaje promedio que sacaron los competidores: una media alta sugiere más puntos parciales accesibles, no más soluciones completas. Consulta también el porcentaje de 100 y los prerrequisitos.
| Problema | Año | Media (puntos parciales) | Lograron 100 |
|---|---|---|---|
| Sorting | 2015 | 47/100 | 18% |
| Overtaking | 2023 | 45/100 | 8% |
| Rarest Insects | 2022 | 35/100 | 3% |
| Distributing Candies | 2021 | 21/100 | 7% |
| Shortcut | 2016 | 18/100 | <1% |
| Partition | 2026 | 18/100 | 2% |
| Aliens | 2016 | 18/100 | <1% |
| Highway Tolls | 2018 | 16/100 | <1% |