Búsqueda binaria en Python: guía completa para una búsqueda eficiente

En términos generales, un algoritmo es una secuencia precisa de instrucciones que sigue un ordenador para realizar una tarea específica o resolver un problema. Consulta la entrada de nuestro blog Qué es un algoritmo para conocer los distintos tipos de algoritmos del machine learning.

Descripción general de conceptos

La búsqueda binaria es un potente algoritmo diseñado para encontrar de forma eficiente un valor en un conjunto de datos ordenado. La idea central de la búsqueda binaria es sencilla: En lugar de comprobar cada elemento del conjunto de datos uno a uno, como en una búsqueda lineal, la búsqueda binaria reduce el intervalo de búsqueda a la mitad con cada paso, lo que hace que el proceso sea mucho más rápido.

Así es como funciona:

1. Empieza comparando el valor objetivo con el elemento medio del conjunto de datos. El índice del valor medio se calcula mediante la fórmula medio = (bajo + alto)/2, donde bajo es el índice del primer elemento del intervalo de búsqueda actual y alto es el índice del último elemento.
2. Compara el valor medio con el objetivo. Si el valor objetivo es igual al elemento del medio, has encontrado el índice y la búsqueda ha terminado. Si el valor objetivo es menor que el elemento del medio, la búsqueda continúa en la mitad izquierda del conjunto de datos. Si el valor objetivo es mayor, la búsqueda continúa en la mitad derecha del conjunto de datos.
3. Repite los pasos 1-2. El intervalo de búsqueda se reduce continuamente a la mitad en cada paso. Repite el proceso hasta encontrar el valor objetivo o hasta que el intervalo de búsqueda quede vacío.

El proceso de búsqueda binaria. Imagen del autor

Arriba tienes un ejemplo simplificado que demuestra el concepto de búsqueda binaria.

Este proceso de reducción a la mitad es lo que hace que la búsqueda binaria sea tan eficiente. Sin embargo, es importante tener en cuenta que el conjunto de datos debe estar ordenado para que la búsqueda binaria funcione correctamente. Si los datos no están ordenados, el algoritmo no funcionará como es debido. 

Consulta Estructuras de datos: una guía completa con ejemplos de Python para saber más sobre los distintos tipos de estructuras de datos que puedes buscar.

Puntos clave que debes recordar

Los siguientes puntos destacan los principios básicos de la búsqueda binaria.

Eficiencia

La búsqueda binaria es mucho más rápida que la búsqueda lineal, sobre todo cuando se trata de grandes conjuntos de datos. Mientras que la búsqueda lineal tiene una complejidad temporal de O(n), lo que significa que puede tener que comprobar cada elemento en el peor de los casos, la búsqueda binaria es más eficiente. Tiene una complejidad temporal de O(log n), lo que significa que el espacio de búsqueda se reduce a la mitad con cada paso, reduciendo significativamente el número de comparaciones necesarias.

Para un desglose detallado de cómo se evalúan los algoritmos, consulta nuestra Guía de notación Big O y complejidad temporal: intuición y matemáticas. Una opción es nuestro tutorial Análisis de la complejidad del código mediante Python.

Requisitos

Para que la búsqueda binaria funcione, el conjunto de datos debe estar ordenado de forma ascendente o descendente. Esto es obligatorio porque el algoritmo se basa en el orden de los elementos para determinar en qué mitad del conjunto de datos debe buscar a continuación. Si los datos no están ordenados, la búsqueda binaria no puede localizar el valor objetivo.

Flexibilidad

La búsqueda binaria puede implementarse de forma iterativa o recursiva. El método iterativo utiliza bucles para reducir repetidamente a la mitad el intervalo de búsqueda. El método recursivo implica que la función se llame a sí misma con un intervalo de búsqueda menor. Esta flexibilidad se presta bien a diferentes aplicaciones.

Aplicaciones del mundo real

La búsqueda binaria es una herramienta poderosa. Su eficiencia a la hora de acotar rápidamente los intervalos de búsqueda hace que tenga un valor incalculable, sobre todo cuando se trata de grandes conjuntos de datos en los que el rendimiento y la velocidad son fundamentales. Exploremos algunas aplicaciones concretas y comparemos la búsqueda binaria con otros algoritmos.

Bases de datos

En las bases de datos, la búsqueda binaria se utiliza a menudo para localizar rápidamente registros dentro de campos ordenados, como cuando se busca un usuario concreto en una base de datos ordenada por ID de usuario. Imagina una base de datos con millones de registros. Una búsqueda lineal requeriría analizar cada registro uno por uno, lo que podría llevar un tiempo considerable. En cambio, la búsqueda binaria puede localizar rápidamente el registro deseado reduciendo sistemáticamente a la mitad el espacio de búsqueda, lo que disminuye de forma considerable el número de comparaciones necesarias.

Ciencia de datos

Buscar en grandes conjuntos de datos ordenados es una tarea habitual en la ciencia de datos. Por ejemplo, en el análisis de series temporales, se puede utilizar la búsqueda binaria para encontrar marcas de tiempo específicas dentro de una secuencia ordenada de eventos. En el machine learning, los algoritmos de búsqueda binaria pueden utilizarse para optimizar los hiperparámetros encontrando el mejor valor dentro de un intervalo.

Computación gráfica

En computación gráfica, la búsqueda binaria se utiliza en algoritmos en los que se necesita precisión y velocidad. Un ejemplo es el trazado de rayos, una técnica de renderización utilizada para simular cómo interactúa la luz con los objetos. La búsqueda binaria puede utilizarse para encontrar rápidamente puntos de intersección entre rayos y superficies.

Componentes para algoritmos complejos

La búsqueda binaria no solo es útil por sí misma, sino que también es un componente de algoritmos y estructuras de datos más complejos. Por ejemplo, los árboles de búsqueda, como los árboles binarios de búsqueda (BST), y los árboles equilibrados, como los árboles AVL, se basan en los principios de la búsqueda binaria. Estas estructuras permiten operaciones eficientes de búsqueda, inserción y eliminación, por lo que son útiles cuando los datos deben actualizarse dinámicamente y deben realizarse búsquedas en ellos con frecuencia. Obtén más información sobre estos árboles en Árbol AVL: guía completa con implementación en Python.

Búsqueda binaria frente a otros algoritmos de búsqueda

Comparemos la búsqueda binaria con otros dos algoritmos de búsqueda habituales: la búsqueda lineal y la búsqueda hash.

Búsqueda lineal

La búsqueda lineal es un algoritmo sencillo que examina secuencialmente cada elemento de un conjunto de datos. Es bastante menos eficiente que la búsqueda binaria, con una complejidad temporal de O(n). Sin embargo, la búsqueda lineal no requiere que los datos estén ordenados, lo que la hace útil en algunos casos.

Búsqueda hash

La búsqueda hash es un algoritmo eficiente para encontrar rápidamente valores en un conjunto de datos cuando esos valores están asociados a claves únicas. Funciona aplicando una función hash a la clave, que calcula un índice donde se almacena el valor correspondiente en una tabla hash. Esto permite una recuperación casi instantánea de los valores, a menudo en tiempo O(1). Sin embargo, aunque la búsqueda hash es muy rápida para encontrar elementos concretos, requiere memoria adicional para almacenar la tabla hash y no es adecuada para buscar dentro de un intervalo de valores, tarea en la que la búsqueda binaria es más apropiada.

Implementación de la búsqueda binaria en Python

Exploremos algunas formas de implementar una búsqueda binaria sencilla en Python. Pero antes tenemos que establecer un conjunto de datos sencillo con el que trabajar y un valor objetivo que buscar. Imagina que tenemos la matriz ordenada y el objetivo de búsqueda siguientes:

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 56

Método iterativo

El método iterativo es quizá el enfoque más sencillo. Con este método, utilizamos un bucle while para dividir repetidamente el intervalo de búsqueda por la mitad hasta que encontremos nuestro objetivo. Este método suele ser el preferido por su claridad y eficiencia.

A continuación te explicamos cómo puedes implementar la búsqueda binaria de forma iterativa:

def binary_search_iterative(arr, target):
    # Define the search bounds
    left, right = 0, len(arr) - 1  
    while left <= right:
        # Calculate the middle index
        mid = left + (right - left) // 2  
        # If the middle element is the target, return its index
        if arr[mid] == target:
            return mid  
        # If the target is bigger, narrow the search to the right half
        elif arr[mid] < target: 
            left = mid + 1  
        # If the target is smaller, narrow the search to the left half
        else: 
            right = mid - 1  
    # Return -1 if the target is not found
    return -1 
    
# Run the iterative function
result = binary_search_iterative(arr, target)
if result != -1:
    print(f"Iterative: Target found at index {result}")
else:
    print("Iterative: Target not found")

Veamos más detenidamente este código:

• Empezamos fijando "izquierda" y "derecha" como límites del espacio de búsqueda. Inicialmente, izquierda es 0 (el principio de la matriz), y derecha es len(arr) - 1 (el final de la matriz).

• En cada iteración, calculamos el índice medio, que representa la mitad del intervalo de búsqueda actual. Para ello se utiliza la fórmula mid = left + (right - left) /2.

• A continuación, comparamos el elemento de mid con target:

• Si coinciden, hemos encontrado nuestro objetivo y la función devuelve mid.

• Si el elemento de mid es menor que el objetivo, significa que el objetivo debe estar en la mitad derecha, así que ajustamos left a mid + 1.

• Si el elemento de mid es mayor que el objetivo, el objetivo debe estar en la mitad izquierda, así que ajustamos right a mid - 1.

• El bucle continúa hasta que se encuentra el objetivo o hasta que left supera right, lo que significa que el objetivo no está en la matriz.

Método recursivo

El método recursivo de búsqueda binaria es otra forma de implementar este algoritmo. En lugar de utilizar un bucle, la función se llama a sí misma, ajustando los límites de búsqueda cada vez hasta que encuentra el objetivo o determina que el objetivo no está presente.

A continuación te explicamos cómo puedes implementar la búsqueda binaria de forma recursiva:

def binary_search_recursive(arr, target, left, right):
    # If the search bounds cross, the target isn't in the array
    if left > right:  
        return -1
    # Calculate the middle index
    mid = left + (right - left) // 2 
    # If middle value equals the target, return the index
    if arr[mid] == target: 
        return mid  
    # If the target is bigger than the middle value, search in the right half
    elif arr[mid] < target: 
        return binary_search_recursive(arr, target, mid + 1, right)  
    # If the target is smaller than the middle value, search in the left half
    else: 
        return binary_search_recursive(arr, target, left, mid - 1)  

# Run the recursive function
result = binary_search_recursive(arr, target, 0, len(arr) - 1)

if result != -1:
    print(f"Iterative: Target found at index {result}")
else:
    print("Iterative: Target not found")

Veamos más detenidamente este código:

• La función recursiva comienza con los mismos límites iniciales left y right que la función iterativa.

• Primero comprueba si left supera right. Si es así, la función devuelve -1, indicando que el objetivo no está en la matriz.

• En caso contrario, la función calcula el índice mid y compara el objetivo con el elemento de mid.

• Si el objetivo es igual al elemento de mid, la función devuelve mid.

• Si el objetivo es mayor que mid, la función se llama a sí misma recursivamente con los límites actualizados para buscar la mitad derecha.

• Si el objetivo es menor que mid, la función busca en la mitad izquierda.

• La recursividad continúa hasta que encuentra el objetivo o agota el espacio de búsqueda.

Para saber más sobre las funciones recursivas, consulta Comprender las funciones recursivas en Python.

Utilizar el módulo bisect integrado de Python

La biblioteca estándar de Python incluye el módulo bisect, que proporciona funciones de búsqueda binaria preimplementadas. Este módulo es muy eficiente y a menudo puede ahorrarnos tiempo respecto a la construcción de nuestra propia función.

Así es como podemos utilizar el módulo bisect para encontrar el objetivo en nuestra matriz:

# Import the bisect module
import bisect 

# Call the module and provide the array and the target value
index = bisect.bisect_left(arr, target) 

#Print results
if index < len(arr) and arr[index] == target:
    print(f"Bisect: Target found at index {index}")
else:
    print("Bisect: Target not found")

Veamos más detenidamente este código:

• La función bisect_left devuelve el índice donde debe insertarse el objetivo para mantener el orden de la matriz. Si el objetivo se encuentra en este índice, significa que el objetivo existe en la matriz.

• Este método es especialmente útil cuando se trabaja con matrices ordenadas y también puede utilizarse para insertar elementos manteniendo el orden.

• El módulo bisect también proporciona otras funciones como bisect_right y insort, que pueden utilizarse para encontrar puntos de inserción o para insertar elementos directamente.

Complejidad temporal y espacial

Cuando hablamos de la eficiencia de un algoritmo, a menudo utilizamos la notación Big O, representada como O(x), para describir cómo crecen los requisitos de tiempo de ejecución o de espacio a medida que aumenta el tamaño de la entrada. Para la búsqueda binaria, la complejidad temporal suele ser O(log n). Esto significa que, a medida que crece el conjunto de datos, el número de operaciones necesarias para encontrar el objetivo aumenta logarítmicamente, lo que hace que la búsqueda binaria sea eficiente incluso para grandes conjuntos de datos.

El método iterativo de búsqueda binaria tiene una complejidad temporal de O(log n) porque el intervalo de búsqueda se reduce a la mitad con cada iteración. Su complejidad espacial es O(1), ya que utiliza una cantidad constante de espacio adicional y solo requiere unas cuantas variables para rastrear los límites de búsqueda y el elemento medio.

El método recursivo también tiene una complejidad temporal de O(log n) por la misma razón. Sin embargo, su complejidad espacial es O(log n) debido al espacio necesario para mantener la pila de llamadas para cada llamada recursiva. Como cada llamada recursiva añade una capa a la pila, la profundidad de la recursividad es proporcional al número de pasos de reducción a la mitad, que es logarítmico en relación con el tamaño del conjunto de datos.

Aunque ambos métodos son eficientes en cuanto a tiempo, el enfoque iterativo es más eficiente en cuanto a espacio. Por eso el módulo bisect utiliza un enfoque iterativo. Personalmente, prefiero el enfoque iterativo también por esta razón. Sin embargo, el enfoque recursivo puede ser más intuitivo para algunas personas y puede requerir menos líneas de código.

Dificultades comunes y cómo evitarlas

Al utilizar una búsqueda binaria, hay que tener cuidado con algunas dificultades comunes. Estas pueden afectar a la corrección y eficiencia de tu algoritmo, por lo que es importante tomar nota de ellas.

En primer lugar, la búsqueda binaria depende de que el conjunto de datos esté ordenado. Si los datos no están ordenados, la búsqueda binaria no funcionará correctamente; puede devolver resultados incorrectos o fallar por completo. Por lo tanto, es esencial ordenar nuestro conjunto de datos antes de aplicar la búsqueda binaria. Si no es posible ordenar los datos, la búsqueda binaria no es la herramienta adecuada.

Un problema frecuente son los errores por uno. Estos errores se producen cuando los cálculos del índice son ligeramente incorrectos, lo que puede provocar bucles infinitos o no localizar el valor objetivo. Esto puede ocurrir si el cálculo del punto medio o los ajustes de los límites no se gestionan con precisión. Para evitarlo, asegúrate de que los cálculos del índice medio sean correctos y de que los límites se actualicen adecuadamente después de cada comparación. Recuerda que los valores de índice en Python empiezan en 0, no en 1.

Otro problema que debes tener en cuenta si utilizas la búsqueda binaria de forma recursiva son los problemas de profundidad de la recursividad. En Python, hay un límite en el número de llamadas recursivas que se pueden hacer, para impedir un uso excesivo de memoria. Si tu conjunto de datos es muy grande, la recursividad profunda podría superar este límite, provocando un desbordamiento de pila. Para mitigarlo, considera la posibilidad de utilizar un enfoque iterativo para la búsqueda binaria, que no sufre las limitaciones de profundidad de recursividad. Si la recursividad es preferible o necesaria, puedes aumentar el límite de recursividad utilizando sys.setrecursionlimit(), pero debes hacerlo con precaución para evitar otros posibles problemas.

Conclusión

La búsqueda binaria es un algoritmo potente y eficaz que debería estar en la caja de herramientas de todo desarrollador de Python. Tanto si se implementa de forma iterativa como si se implementa de forma recursiva, ofrece una importante ventaja de rendimiento sobre la búsqueda lineal, especialmente con grandes conjuntos de datos. Para saber más, consulta el programa de competencias Programación en Python de DataCamp o el curso interactivo Principios de ingeniería de software en Python.