Búsqueda binaria e invariante
Mapa conceptual
La idea
Sobre un arreglo ORDENADO, se compara con el elemento del medio. Si el buscado es menor, todo el lado derecho queda descartado; si es mayor, el izquierdo. Se repite sobre el rango restante, que se reduce a la mitad en cada paso: log₂ n pasos para n elementos.
El invariante
La corrección se demuestra con un invariante: «si el valor existe, está dentro del rango [lo, hi]». Se cumple al inicio (el arreglo entero) y cada paso lo preserva: descartamos solo elementos que ya sabemos que no pueden ser la solución. Cuando el rango se vacía, el valor no existe.
[Comparaciones en el peor caso]
Esta actividad interactiva ('Grafico interactivo') requiere el motor completo de Lumbre. El contenido estatico se muestra arriba; para la experiencia interactiva, visita la version online de este objeto.
Cuidado con el medio
El índice medio se calcula como lo + (hi − lo)//2, NO como (lo + hi)//2, para evitar desbordamiento de entero en lenguajes de tamaño fijo. Es un error famoso: el código de Java de la biblioteca estándar lo tuvo durante años.
| Elemento | Rol en el invariante | Error típico |
|---|---|---|
| lo | extremo inferior vivo | olvidar que está incluido |
| hi | extremo superior vivo | mezclar rangos cerrados y abiertos |
| mid | la comparación | usar (lo+hi)//2 con overflow |
| retorno | posición o no-existe | confundir no encontrado con índice 0 |
¿Qué debe cumplirse para poder aplicar búsqueda binaria?
Más allá de «encontrar»
La búsqueda binaria resuelve una clase amplia: buscar la primera posición que cumple una condición monótona (bisecar una función, encontrar dónde insertar, contar elementos menores). En todos, el motor es el mismo invariante sobre un rango.
Versiones y rangos
- Rango cerrado [lo, hi]: se termina cuando lo mayor que hi.
- Rango semicerrado [lo, hi): se termina cuando lo igual a hi.
- Mezclar ambas convenciones en un mismo código es la fuente nº1 de bugs; elige una y sé disciplinado.
El costo de log n
Para un millón de elementos, log₂ es unos 20 pasos. Para mil millones, 30. La búsqueda binaria hace que crecer mil veces apenas cueste algunos pasos más: por eso escala tan bien.
La búsqueda binaria funciona sobre una lista enlazada ordenada con costo O(log n).
Errores frecuentes
- Buscar en datos desordenados y no notarlo.
- Mover los límites incorrectamente (usar mid en lugar de mid±1) y provocar bucles infinitos.
- Devolver el último mid como si fuera la solución cuando el valor no está.
Ordena los pasos de la búsqueda binaria:
Inicio
Ciclo
Fin
Wikipedia
Búsqueda binaria, variantes y el problema del overflow.
Escribe el invariante de la búsqueda binaria para «primera posición cuyo valor es mayor o igual a x» (biseca a la izquierda). Explica cómo cambian lo e hi y por qué el rango se reduce sin perder la solución.
VisuAlgo
Visualizaciones animadas de estructuras de datos y algoritmos.