La búsqueda binaria (binary search) en Python
En esta lección vas a implementar la búsqueda binaria para encontrar rápidamente un valor en una lista ordenada.
Introducción
El problema
Buscar un valor en una lista de un millón de elementos revisándolos uno a uno puede costar un millón de comparaciones. Si la lista está ordenada, puedes hacerlo mucho mejor: bastan unas 20 comparaciones, porque cada comprobación descarta la mitad de lo que queda.
Imagínalo así
La búsqueda binaria es como buscar una palabra en un diccionario de papel. Lo abres por la mitad, miras si tu palabra va antes o después de esa página y descartas la mitad donde no puede estar. Repites con la mitad que queda hasta llegar a la palabra.
low, high = 0, len(values) - 1📖 Las páginas que aún tienes que revisarmiddle = (low + high) // 2👆 Abre por la mitadlow = middle + 1➡️ La palabra va después: descarta la primera mitadhigh = middle - 1⬅️ La palabra va antes: descarta la segunda mitadLa búsqueda binaria encuentra un valor en una lista ordenada comparándolo una y otra vez con el elemento del medio y descartando la mitad donde no puede estar. Tarda O(log n) pasos.
Puntos clave
lowyhighmarcan la parte de la lista donde todavía puede estar el valor buscado.middle = (low + high) // 2elige el índice del medio de esa parte.- Si
values[middle] < target, el valor está a la derecha, así quelow = middle + 1; si no,high = middle - 1. while low <= high:se detiene cuando el rango queda vacío, y la función devuelve-1si no lo encuentra.- Para 17, la búsqueda revisa 12, luego 25 y luego 17: tres comparaciones en lugar de cuatro.
¿Cuándo se usa?
- Buscar en grandes volúmenes de datos ordenados: IDs, diccionarios, logs (registros) ordenados.
- Encontrar dónde insertar un valor para que una lista siga ordenada.
- Juegos de adivinar números y cualquier problema en el que puedas acotar la respuesta con pistas de más alto o más bajo.
Cuándo no hace falta
- Los datos no están ordenados: ordenar solo para buscar una vez cuesta más que una búsqueda lineal.
- Listas pequeñas o búsquedas puntuales:
ino un diccionario es más sencillo; para muchas búsquedas por clave, un dict o un set es aún más rápido.
Visualizador de La búsqueda binaria (binary search) en Python
O(log n)Usa Reproducir o Paso para seguir cada comparación y movimiento de datos.
Código de ejemplo
def binary_search(values, target):
low, high = 0, len(values) - 1
while low <= high:
middle = (low + high) // 2
if values[middle] == target:
return middle
if values[middle] < target:
low = middle + 1
else:
high = middle - 1
return -1
print(binary_search([3, 8, 12, 17, 25, 31], 17))
Resultado de la ejecución
3
Explicación del código
Las variables low y high delimitan la zona que queda por explorar. Si el elemento del medio es menor que el valor buscado, el algoritmo descarta la mitad izquierda con low = middle + 1; si no, descarta la mitad derecha. La complejidad en tiempo es O(log n), siempre que la lista de entrada ya esté ordenada.
Cambia los valores y ejecuta el programa en el compilador Python online de CodeUtility sin instalar Python.
Ejercicios de práctica
Prueba a modificar el código siguiendo las ideas de abajo. Cambiar el código y ver el resultado te ayudará a entender la lección mucho mejor que solo leerla.
- Prueba con una lista vacía, una lista de un solo elemento y una lista con repetidos.
- Muestra el estado después de cada paso para ver el algoritmo en acción.
- Mide el tiempo de ejecución con 100, 1.000 y 10.000 elementos y compáralo con otra solución.
Errores comunes
Usar < en lugar de <= en el bucle
Con low < high, un valor en la última posición que queda nunca se comprueba.
while low < high:
while low <= high:
No avanzar más allá del medio
Con low = middle, el mismo medio se puede repetir para siempre.
low = middle
low = middle + 1
¿Terminaste esta lección?
Márcala como aprendida para seguir tu progreso.
Practica con un reto
Usa lo que cubre esta lección para resolver un problema real. Cada reto se ejecuta en el navegador, con pruebas al instante y una revisión de IA.
- Tiempo de Producción en Fábrica Encuentra el tiempo más temprano en que máquinas en paralelo pueden terminar una cantidad objetivo de productos. Intermedio
- Mediana de Dos Arreglos Ordenados Encuentra la mediana de dos listas ordenadas combinadas. Difícil