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.

ProblemaCompetenciaDificultad
Bicicleta2016 Nacional🟢 fácil
Paltas2023 Regional🟡 media
Teletransportador cuántico de flujos2017 Clasificatoria🟡 media
La leyenda de Zolda2017 Nacional🟡 media
Reloj inteligente2018 Regional🟡 media
Cine2024 Nacional🟡 media
La leyenda de Zolda2017 Regional🔴 difícil
Catalonia2020 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.

ProblemaAñoMedia (puntos parciales)Lograron 100
Sorting201547/10018%
Overtaking202345/1008%
Rarest Insects202235/1003%
Distributing Candies202121/1007%
Shortcut201618/100<1%
Partition202618/1002%
Aliens201618/100<1%
Highway Tolls201816/100<1%