PROGRAMAR ALGORITMO DE BÚSQUEDA BINARIA CON PYTHON

Hola a todos:

Hace unos días me encontré con el concepto de algoritmo de búsqueda binaria en Python. En concreto, y reproduzco de la Wikipedia:
«es un algoritmo de búsqueda que encuentra la posición de un valor en un array ordenado. 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 y la búsqueda continúa en la mitad restante hasta que el valor se encuentre«.

Es importante tener muy en cuenta que funcionaré si el array está ordenado, y esto tiene dos consecuencias, si nuestro array (arreglo) no está ordenado, pero permite que se pueda ordenar, no hay problema lo solucionamos con un .Sort(), pero si no se puede ordenar (por le motivo que sea), entonces este algoritmo no funcionaría o no sería de utilidad y tendríamos que recurrir a otro.

Pues vamos a tener en cuenta que sí lo podemos ordenar con .Sort. Este sería nuestro arreglo:

miArray = [11, 2, 25, 3, 21, 19, 4, 10, 40 ]

y debemos tener en cuenta que el algoritmo se puede programar de dos formas, una con método recursivo y otro iterando los elementos en un loop while.

El primer, con método recursivo sería este:

def busqueda_bin(miArray, ini, fin, num):
    if fin >= ini:
        med = (ini + fin) // 2
        #si num está la media devuelve med
        if miArray[med] == num:
            return med
        #si num es menor a media num está en array izquierdo
        elif miArray[med] > num:
            return busqueda_bin(miArray, ini, med - 1, num)
        else:
        # de lo contrario num estará en array derecho  
            return busqueda_bin(miArray, med + 1, fin, num)
    else:
        #si fin es menor que ini devolvemos falso
        return False
#componemos o importamos arreglo        
miArray = [11, 2, 25, 3, 21, 19, 4, 10, 40 ]
#ordenamos arreglo
miArray.sort()
#indicamos número a buscar
num =25
#resultado de la función
final = busqueda_bin(miArray, 0, len(miArray)-1, num)
if final == False:
    print("No encontrado")
else:
    print("El número se encuentra en la lista: " + str(miArray) + " en la posición: ", str(final))

El resultado de buscar el número 25 es el siguiente:

El número se encuentra en la lista: [2, 3, 4, 10, 11, 19, 21, 25, 40] en la posición:  7

Como podéis observar en la salida he incluido el array ya ordenado para comprender y ver mejor de donde sale el resultado. Por cierto, como en todos los array, estamos hablando de base 0, el 2 sería el 0 y el 3 el 1 …etc.

Para completar con el método iterativo, esté sería el código con idéntica respuesta:

def busqueda_bin(miArray,num):
    ini = 0
    fin = len(miArray)-1
    salida = False
    while(ini<=fin and not salida):
        med = (ini + fin)//2
        #si es igual a med, num está en la mitad
        if miArray[med] == num :
            salida = med
        else:
            #si num es menor que la mitad, está en array izquierdo
            if num < miArray[med]:
                fin = med - 1
            else:
            # de lo contrario está en array derecho    
                ini = med + 1
    return salida
#componemos o importamos arreglo    
miArray=[11, 2, 25, 3, 21, 19, 4, 10, 40]
#ordenamos arreglo
miArray.sort()
#indicamos número a buscar
num= 25
#obtenemos resultado
final= (busqueda_bin(miArray, num))
if final == False:
    print("No encontrado")
else:
    print("El número se encuentra en la lista: " + str(miArray) + " en la posición: ", str(final))

Como se puede apreciar estamos utilizando un loop While para iterar sobre los elementos de nuestro arreglo.

En resumen, es un ejercicio que puede ser interesante en determinadas ocasiones, aunque debemos tener en cuenta que tenemos multitud de alternativas.

Espero que sea de utilidad!!

¿Te ha resultado de interés?, puedes apoyar a Excel Signum con una pequeña donación.



¡¡Muchas gracias!!

Mediante la suscripción al blog, la realización comentarios o el uso del formulario de contacto estás dando tu consentimiento expreso al tratamiento de los datos personales proporcionados según lo dispuesto en la ley vigente (LOPD). Tienes más información al respecto en esta página del blog: Política de Privacidad y Cookies