Búsqueda binaria
Encuentra un valor en un arreglo ordenado mirando el centro y descartando la mitad donde no puede estar. Cada comparación reduce a la mitad lo que queda.
- mejor caso Ω(1)
- caso medio Θ(log n)
- peor caso O(log n)
- espacio O(1)
¿Qué significan estos términos?
- Ordenado: en orden creciente. La búsqueda binaria lo necesita; con datos desordenados da respuestas erróneas.
- Partir por la mitad: cada comparación descarta la mitad de lo que queda, la mitad donde el objetivo no puede estar.
- log₂ n: cuántas veces se puede partir n por la mitad hasta llegar a 1. Para 64 valores son 6, así que 7 comparaciones como mucho.
- centro (mid)
- encontrado
- descartado
- objetivo
Cada centro que la búsqueda podría elegir; una ejecución es un camino hacia abajo. Niveles: 5 = ⌈log₂(24 + 1)⌉, el máximo de comparaciones que puede necesitar.
Busco 70 entre 24 valores ordenados: todavía está en juego todo el arreglo.
Espacio: reproducir o pausar. Flechas izquierda y derecha: paso a paso. Inicio y Fin: saltar.
Prueba esto: Elige un objetivo que no esté en el arreglo. La búsqueda igualmente termina tras como mucho ⌈log₂(n + 1)⌉ comparaciones, cuando lo supera a hi.
Cómo funciona
La búsqueda binaria mantiene dos marcas, lo y hi, alrededor de la parte del arreglo donde el objetivo aún puede estar. Mira el valor del centro: si es el objetivo, termina; si es menor, el objetivo solo puede estar a la derecha, así que lo pasa detrás del centro; si es mayor, hi pasa delante. Cada paso reduce el resto a la mitad: 64 valores necesitan como mucho 7 comparaciones y un millón como mucho 20. Cuando lo supera a hi, no queda nada: el valor no está en el arreglo.
Cuándo es una buena opción
Usa la búsqueda binaria siempre que los datos estén ordenados y puedas saltar a cualquier posición: una palabra en una lista ordenada, una versión en un historial, git bisect, el sitio donde insertar en un arreglo ordenado. Con datos desordenados da respuestas erróneas, y ordenar antes solo compensa si buscas muchas veces.