La búsqueda binaria es uno de los algoritmos más elegantes de la programación. Permite encontrar un elemento en una lista ordenada con una eficiencia espectacular: en lugar de revisar elemento por elemento, divide el espacio de búsqueda por la mitad en cada paso.
El problema que resuelve
Imagina que tienes una lista de 1.000.000 de números ordenados y quieres encontrar uno concreto. Con búsqueda lineal (revisar uno a uno) necesitarías hasta 1.000.000 comparaciones. Con búsqueda binaria, necesitas como máximo 20 comparaciones.
¿Cómo funciona?
- Mira el elemento del centro de la lista.
- Si es el que buscas, ¡encontrado!
- Si el elemento buscado es menor, descarta la mitad derecha.
- Si es mayor, descarta la mitad izquierda.
- Repite con la mitad restante.
Implementación en Python
def busqueda_binaria(arr, objetivo):
izquierda, derecha = 0, len(arr) - 1
while izquierda <= derecha:
medio = (izquierda + derecha) // 2
if arr[medio] == objetivo:
return medio # Encontrado en posición 'medio'
elif arr[medio] < objetivo:
izquierda = medio + 1 # Buscar en mitad derecha
else:
derecha = medio - 1 # Buscar en mitad izquierda
return -1 # No encontrado
numeros = [2, 5, 8, 12, 16, 23, 38, 45, 67, 91]
print(busqueda_binaria(numeros, 23)) # Output: 5 (índice)Complejidad: O(log n)
Cada paso elimina la mitad de los candidatos. Para 1.000.000 elementos: log₂(1.000.000) ≈ 20 pasos. Para 1.000.000.000 elementos: solo 30 pasos.
Requisito fundamental
La lista debe estar ordenada. Si no lo está, la búsqueda binaria no funciona. En ese caso hay que ordenarla primero (coste O(n log n)) o usar búsqueda lineal directamente.