0

Me preguntaba como poder hacer una búsqueda dentro de un arreglo, o lista, que sea eficiente. He investigado y leído sobre algoritmos de búsqueda, y me encontré con el término de búsqueda binaria. Estaría bien recebir ayuda.

¡Muchas gracias!

3
  • Buen día, la respuesta que pusiste es parte de la pregunta? Si es así, por favor edita la pregunta, agrega la información y elimina la respuesta el 14 jun. 2022 a las 6:38
  • La respuesta va aparte, gracias por decirmelo, debería haberlo aclarado. el 14 jun. 2022 a las 6:53
  • 1
    No necesitas implementar búsquedas en python. El lenguaje te da ya esa funcionalidad. Por ejemplo 3 in lista te retorna True si el valor 3 aparece en la lista. O bien lista.index(3) te devuelve el índice en que el 3 aparece. Internamente esas operaciones están implementadas de forma eficiente, aunque van a requerir más tiempo cuanto mayor sea la lista (complejidad O(N)). Para tener tiempos independientes del tamaño deberías usar conjuntos o diccionarios.
    – abulafia
    el 14 jun. 2022 a las 10:01

1 respuesta 1

0

El algoritmo de Búsqueda Binaria solo se puede aplicar a arreglos, o listas, que estén estrictamente ordenadas, da igual de menor a mayor, o de mayor a menor, pero estrictamente deben estar ordenadas.

Para poder crear este algoritmo en python, deberemos crear una lista por ejemplo:

fList = [1,2,3,4,5,6,7,8,9]

Y una variable que sea el número a buscar, ya puede ser pidiéndolo por consola o escribiéndolo previamente, por ejemplo:

x = int(input("Numero del arreglo a elegir: "))

or

x = 2

Después de haber establecido el número a buscar y la lista donde lo buscaremos, empezaremos a trabajar con el algoritmo de búsqueda.

Cosas a entender antes de trabajar con el algoritmo de Búsqueda Binaria:

  • Deberemos establecer tanto el numero final de nuestra lista, que sería el último indice de nuestra lista, como el primer numero de nuestra lista, que siempre es 0.

  • Habrá que establecer un numero entero que sea el que esté siempre en la mitad del rango de búsqueda.

  • El algoritmo basa su búsqueda en acortar el índice de nuestra lista hasta encontrar el número especificado, no es un algoritmo de comparación de datos, cual procesamiento es cuadrático.

Después de conocer esto, procedemos con el código, que sería éste:

def main():
    
    lista = [1,8,6,4,8,5,12,455,78,41,50,90,1100,548,523,658,987,4125,32145,248652,45524,822445,11,5,16,5465,4,465,42321,65,45,153,54,9,5436,515645,65,6]
    x = 65

    binarySearch(lista, x)



def binarySearch(lista, x):

    left = 0
    right = len(lista) - 1
    mid = 0

    lista.sort()


    while(left <= right):


        mid = (left+right) // 2

        if lista[mid] < x:

            left = mid + 1
            print("Current left is: {}".format(left))
            print("Current right is: {}".format(right))

        if lista[mid] > x:

            right = mid - 1
            print("Current left is: {}".format(left))
            print("Current right is: {}".format(right))

        if lista[mid] == x:

            print("EL numero está en la posicion: {}".format(mid))
            break

        if x not in lista:

            print("El numero no esta")
            break


if __name__ == "__main__":
    main()

Como podemos ver, el numero del medio deberá ser siempre la mitad rango de nuestros índices izquierda y derecha, que se hace con la simple operación de la suma del índice izquierdo e índice derecho dividiédolo entre dos como un entero (Para dividir y que nuestro resultado sea entero, se usa //)

Funcionamiento del algoritmo escrito:

  • Se define la lista.
  • Se define el número a buscar dentro de la lista.
  • Se establecen las posiciones de los índices de la lista anteriormente definida de izquierda, derecha y medio.
  • Creamos el bucle de búsqueda con la condición de que izquierda debe ser siempre más pequeño que derecha. -Creamos el cálculo de el índice medio dentro del bucle. (Medio cambia por cada pasada del bucle, debido a que el rango se hará más pequeño o más grande.)
  • Creamos las condiciones de que si el numero que está en el índice de medio es más pequeño que la mitad de nuestro rango, el índice derecho pasará a tener el mismo índice que medio mas uno; si el número a buscar es mayor que el número en el índice medio, la posición left pasará a ser igual que la posición media menos uno.; Si el número a buscar está en la posición mid, es que hemos encontrado el numero. Y si numero a buscar no está en la lista que nos diga que no está dentro de la lista.
1
  • Hay un error en mid = (left+right) // 2.
    – Candid Moe
    el 14 jun. 2022 a las 9:18

Tu Respuesta

Al pulsar en “Publica tu respuesta”, muestras tu consentimiento a nuestros términos de servicio, política de privacidad y política de cookies

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.