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

Imágen de perfil
Val: 1.437
Oro
Ha mantenido su posición en Python (en relación al último mes)
Gráfica de Python

Algoritmo de búsqueda binariagráfica de visualizaciones


Python

Publicado el 3 de Agosto del 2018 por xve
3.753 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

Publicado el 3 de Agosto del 2018gráfica de visualizaciones de la versión: Versión 1
3.754 visualizaciones desde el 3 de Agosto del 2018
estrellaestrellaestrellaestrellaestrella
estrellaestrellaestrellaestrella
estrellaestrellaestrella
estrellaestrella
estrella

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
"""
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 (0)


No hay comentarios
 

Comentar la versión: Versión 1

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad

http://lwp-l.com/s4739