Código de Python - Algoritmo de búsqueda binaria

Pos: 3

Val: 2.239

Ha mantenido su posición en Python (en relación al último mes)

Algoritmo de búsqueda binaria

Python

(1)

Publicado el 3 de Agosto del 2018 por Xve (294 códigos)

15.663 visualizaciones desde el 3 de Agosto del 2018

El algoritmo de búsqueda binaria, se posiciona en el medio del array y determina si el valor a buscar es superior o inferior. Luego busca la mitad de la parte superior o inferior según resultado anterior hasta dar con el valor.
Este algoritmo es mas optimo que la búsqueda lineal (https://www.lawebdelprogramador.com/codigo/Python/4738-Algoritmo-de-busqueda-lineal.html) que busca uno a uno.

Necesita utilizar un array o lista ordenada.

Versión 1
(1)

Publicado el 3 de Agosto del 2018

gráfica de visualizaciones de la versión: Versión 1

15.664 visualizaciones desde el 3 de Agosto del 2018

"""

El algoritmo de busqueda binaria, se posiciona en el medio del array y

determina si el valor a buscar es superior o inferior. Luego busca la mitad de

la parte superior o inferior segun resultado anterior hasta dar con el valor.

Este algoritmo es mas optimo que la busqueda lineal que busca uno a uno.

Necesita utilizar un array o lista ordenada.

"""

valores=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21]

def busquedaBinaria(buscar,inicio,fin,iteraciones):

"""

    Función recursiva para el algoritmo de busqueda binaria.

    Devuelve dos valores...

        - True o False para determinar si ha encontrado el elemento

        . Numero de interaciones en la lista o array para buscar el elemento

"""

    # buscamos el elemento central del array entre dos posiciones

    centro=int((fin-inicio)/2)+inicio

    if centro>len(valores)-1 or inicio>fin:

        return (False,iteraciones)

    if buscar>valores[centro]:

        return busquedaBinaria(buscar,centro+1,fin,iteraciones+1)

    elif buscar<valores[centro]:

        return busquedaBinaria(buscar,inicio,centro-1,iteraciones+1)

    else:

        return (True,iteraciones)

while True:

    buscar=input("indica un numero a buscar: ")

    if buscar=="":

        break

    try:

        buscar=int(buscar)

    except:

        print("El valor tienes que ser numerico")

        continue

    conseguido,iteraciones=busquedaBinaria(buscar,0,len(valores),1)

    if conseguido:

        print("Encontrado en {} iteraciones".format(iteraciones))

    else:

        print("El valor introducido no se encuentra en la lista de valores. Se han necesitado {} iteraciones".format(iteraciones))

Comentarios sobre la versión: Versión 1 (1)

jaime

26 de Enero del 2021

<h1> Excelente</h1>

Responder

Comentar la versión: Versión 1

http://lwp-l.com/s4739

Algoritmo de búsqueda lineal

Algoritmo ordenado por inserción

Código de Python - Algoritmo de búsqueda binaria

Versión 1(1)

Comentarios sobre la versión: Versión 1 (1)

Comentar la versión: Versión 1

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Versión 1
(1)