Búsqueda Binaria en Python

La búsqueda binaria en Python se puede realizar de diversas formas, a continuación te las explicaré.

 

Antes de nada vamos a entender como funciona. La búsqueda binaria es un algoritmo de búsqueda que encuentra la posición de un valor en un array ordenado (como ordenar un array en Python)

El funcionamiento es el siguiente:

  • Compara el valor con el elemento en el medio del array, si no son iguales, la mitad en la cual el valor no puede estar es eliminada
  • La búsqueda continúa en la mitad restante hasta que el valor se encuentre

funcionamiento busqueda binaria

Algoritmo de búsqueda binaria iterativa

Esta se podría decir que es la versión «fácil» o más entendible.

La idea de la búsqueda binaria como hemos visto es limitar las búsquedas, esto es posible gracias a que el array se encuentra ordenado.

El algoritmo busca de la siguiente forma:

  • Crea dos límites, uno para la parte izquierda del array y otro para la derecha
  • Ejecuta la búsqueda mientras que el límite izquierdo sea menor o igual al derecho
  • En cada iteración del bucle calculamos un punto medio y recalculamos los límites dependiendo si hemos encontrado el elemento o no

Si el elemento que buscamos esta en el array el algoritmo lo va a encontrar en alguna posición que calcule como mitad, ya que vamos acotando la búsqueda en cada iteración

Una posible implementación sería la siguiente:

def binary_search_it(array, x):
    left = 0
    right = len(array) - 1

    while left <= right:
        mid = (left+right)//2
        if array[mid] == x:
            return mid
        elif array[mid] > x:
            right = mid-1
        else:
            left = mid+1
    return -1

Para probar el algoritmo bastaría con el siguiente código:

arr = [0, 2, 3, 4, 5, 6, 7, 9, 89] # Tupla ordenada
print(binary_search_it(arr,9)) # Salida: 7

Algoritmo de búsqueda binaria recursiva

Los algoritmos recursivos suelen ser más complicados de entender, ya que la recursividad es una forma abstracta de programar.

En este caso no es especialmente difícil de entender el algoritmo recursivo si hemos entendido bien la versión iterativa. Vamos a ver primero el algoritmo:

def binary_search_re(array, x, left, right):
    if left > right: # Llamada erronea
        return -1
    
    mid = (left+right)//2
    if array[mid] == x:# Caso base
        return mid
    elif array[mid] > x: # El numero esta a la izquierda
        return binary_search_re(array, x, left, mid-1)
    else: # El numero esta a la derecha
        return binary_search_re(array, x, mid+1, right)

Existen ciertas diferencias con la versión iterativa y son las siguientes:

  • Los límites los introducimos como parámetros, porque en cada llamada recursiva hay que cambiarlos.
  • Al principio de la función se comprueba si los límites introducidos en la invocación son correctos.
  • Calculamos la mitad como antes.
  • Tenemos la misma estructura condicional que antes, con la diferencia que en este caso no actualizamos los límites, sino que llamamos recursivamente a la función los nuevos límites. Al introducir los nuevos límites en la llamada no incluimos el elemento de la mitad, porque lo acabamos de comprobar.

Como he dicho puede resultar complicado de entender, pero como todo es práctica, para entender la recursividad hay que programar recursivamente 🙂

La llamada a la función es parecida a la anterior, con la diferencia que hay que introducir los límites de búsqueda:

arr = [0, 2, 3, 4, 5, 6, 7, 9, 89]
print(binary_search_re(arr, 9, 0, len(arr)-1))

Los límites al principio son la primera posición (la 0) y la última posición de la lista de enteros (longitud de la lista -1, porque empezamos en 0).

 

Deja un comentario