5.2: Búsqueda Binaria

La Búsqueda Binaria es un algoritmo que es altamente eficiente en comparación con la Búsqueda Lineal, siempre que se cumplan ciertas condiciones. En este caso, la Búsqueda Binaria sigue el principio de divide y conquista, del cual hemos hablado en detalle en el Capítulo 4.

Para comprender mejor este concepto, veamos más de cerca cómo funciona. Primero, la Búsqueda Binaria examina el elemento medio de una lista ordenada. Si el valor objetivo es igual a este elemento medio, significa que hemos encontrado con éxito nuestro objetivo y el proceso de búsqueda puede terminar. Sin embargo, si el valor objetivo es menor que el elemento medio, podemos suponer que el valor objetivo no puede encontrarse en la mitad derecha de la lista. Como resultado, el proceso de búsqueda solo continuará en la mitad izquierda de la lista. Por otro lado, si el valor objetivo es mayor que el elemento medio, podemos asumir con seguridad que el valor objetivo no puede encontrarse en la mitad izquierda de la lista. Por lo tanto, el proceso de búsqueda solo continuará en la mitad derecha de la lista.

Este proceso de búsqueda y división del espacio de búsqueda continúa hasta que encontremos el valor objetivo o hasta que el espacio de búsqueda esté vacío. Con cada iteración, el espacio de búsqueda se reduce a la mitad, lo que permite que la Búsqueda Binaria reduzca rápidamente las posibilidades y encuentre el valor objetivo mucho más rápido que la Búsqueda Lineal.

Como prometimos, ahora pasemos a través de un ejemplo de cómo funciona la Búsqueda Binaria y proporcionemos algo de código para ayudar a ilustrar el proceso.

Ahora, ilustremos esto con un ejemplo. Supongamos que tenemos una lista ordenada de números:

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

y queremos encontrar el número 23.

Primero, observamos la mitad de la lista, que es 16. Dado que 23 > 16, sabemos que 23 debe estar en la mitad derecha de la lista.
A continuación, observamos la mitad de la mitad derecha, que es 38. Dado que 23 < 38, sabemos que 23 debe estar en la mitad izquierda de esta sublista ([23, 38]).
Luego, observamos la mitad de [23, 38], que es 23. Dado que 23 == 23, hemos encontrado nuestro objetivo y la búsqueda ha terminado.

Ahora, veamos cómo podemos implementar esto en Python:

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid  # Element found, return its index
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # Element not found

# Test our function
numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(numbers, 23))  # Outputs: 5

En el código Python anterior, definimos una función binary_search que toma una lista ordenada arr y un valor target como entradas. Comienza configurando los punteros left y right al inicio y al final de la lista, respectivamente. Luego, entra en un bucle que continúa hasta que left y right se encuentran.

En cada iteración del bucle, calcula mid, el índice del elemento medio. Si este elemento medio es igual a target, devuelve el índice. Si target es mayor, mueve el puntero left a mid + 1. Si target es menor, mueve el puntero right a mid - 1. Si el bucle se completa sin encontrar el objetivo, devuelve -1, lo que indica que el objetivo no está presente en la lista.

En las siguientes secciones, profundizaremos en la comprensión del rendimiento de la Búsqueda Binaria y cómo se compara con otros algoritmos de búsqueda.

El algoritmo de Búsqueda Binaria demuestra una mejora significativa en la complejidad temporal sobre la Búsqueda Lineal. Cada comparación reduce nuestro espacio de búsqueda a la mitad. Por lo tanto, en una lista de n elementos, en el peor de los casos, necesitaríamos hacer log2(n) comparaciones para encontrar nuestro objetivo o confirmar que no está en la lista.

Dada esta relación logarítmica entre el tamaño de la lista y el número de pasos, decimos que la Búsqueda Binaria tiene una complejidad temporal de O(log n). Recuerda, "log" aquí es base 2, pero en la notación Big O, típicamente ignoramos este detalle, ya que nos interesa principalmente la tasa de crecimiento, no los cálculos específicos.

En cuanto a la complejidad espacial, la Búsqueda Binaria brilla nuevamente: solo necesita una cantidad constante de espacio adicional para almacenar las variables left, right y mid, independientemente del tamaño de la lista. Entonces, la complejidad espacial es O(1), lo que significa que utiliza una cantidad constante de espacio.

Las mejoras en las complejidades temporal y espacial son lo que hacen que la Búsqueda Binaria sea una opción preferida para buscar en listas ordenadas, especialmente cuando el tamaño de la lista es grande. Sin embargo, el requisito de que la lista esté ordenada es un compromiso que debe considerarse.

En resumen, comprender las complejidades de un algoritmo como la Búsqueda Binaria nos permite tomar decisiones informadas sobre qué algoritmos son los más adecuados para resolver problemas específicos, especialmente cuando se trata de restricciones relacionadas con el tiempo y el espacio.