La intuición de la guía telefónica
Para buscar un apellido en una guía telefónica, nadie lee desde la página 1. Abres la mitad, compruebas si el apellido está antes o después, y descartas la mitad del libro. Repites el proceso.
Eso es la búsqueda binaria: cada paso reduce el trabajo a la mitad. Un millón de registros ordenados requieren a lo sumo ~20 comparaciones. La búsqueda lineal en los mismos datos tomaría, en promedio, 500,000 pasos. Esa es la diferencia entre O(log n) y O(n).
def binary_search(values, target):
low, high = 0, len(values) - 1
while low <= high:
mid = (low + high) // 2
if values[mid] == target:
return mid
elif values[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1El balance (trade-off)
La búsqueda binaria es exponencialmente más rápida, pero exige que la lista esté ordenada. Ordenar cuesta O(n log n); por tanto, si buscas una sola vez en datos desordenados, la búsqueda lineal es adecuada. Si vas a realizar *múltiples* búsquedas, ordena una sola vez y busca con binaria para siempre.
Saber evaluar balances como este es el corazón del diseño algorítmico profesional.
Puntos clave
- Búsqueda lineal: O(n), funciona con cualquier lista desordenada.
- Búsqueda binaria: O(log n), requiere datos ordenados previamente.
- Cada paso binario descarta la mitad exacta de los candidatos restantes.
- Elegir un algoritmo implica comprender las características y demandas de tus datos.