Algoritmos en Python

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.

  • Intermedio
  • 2 min de lectura
  • 1 ejemplo ejecutable

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.

Del diccionario de papel al código
low, high = 0, len(values) - 1📖 Las páginas que aún tienes que revisar
middle = (low + high) // 2👆 Abre por la mitad
low = middle + 1➡️ La palabra va después: descarta la primera mitad
high = middle - 1⬅️ La palabra va antes: descarta la segunda mitad
Cada comparación reduce a la mitad lo que queda, así que incluso listas enormes necesitan pocos pasos.
En una frase

La 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

  1. low y high marcan la parte de la lista donde todavía puede estar el valor buscado.
  2. middle = (low + high) // 2 elige el índice del medio de esa parte.
  3. Si values[middle] < target, el valor está a la derecha, así que low = middle + 1; si no, high = middle - 1.
  4. while low <= high: se detiene cuando el rango queda vacío, y la función devuelve -1 si no lo encuentra.
  5. 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: in o 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

Ejecutar código →
main.py
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))
Obtén un botón Run para este ejemplo

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.

  1. Prueba con una lista vacía, una lista de un solo elemento y una lista con repetidos.
  2. Muestra el estado después de cada paso para ver el algoritmo en acción.
  3. Mide el tiempo de ejecución con 100, 1.000 y 10.000 elementos y compáralo con otra solución.
Ejecutar en el compilador de Python →

Errores comunes

Usar < en lugar de <= en el bucle

Con low < high, un valor en la última posición que queda nunca se comprueba.

Problema
while low < high:
Solución
while low <= high:

No avanzar más allá del medio

Con low = middle, el mismo medio se puede repetir para siempre.

Problema
low = middle
Solución
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.

Todos los retos