python_studies/algoritmos_busca.py at main · ODenteAzul/python_studies · GitHub

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
"""
Algoritmo de busca linear
Se a lista é ordenada podemos verificar se o número atual é
maior que o número buscado e assim interromper a busca poupando
recursos computacionais
"""
def busca_valor(lista,alvo):
    controle = 0
    achou = False
    stop = False
    while controle < len(lista) and not achou:
        if lista[controle] == alvo:
            achou = True
        else:
            if lista[controle] > alvo:
                stop = True
            else:
                controle = controle + 1
    return achou

lista1 = [1,2,3,4,5,7,8,9,10,15,16,17,20,31,32,33,34,35]

print('Busca linear:',busca_valor(lista1,10))
print('Busca linear:',busca_valor(lista1,40))

"""
Algoritmo de busca binária
Lista TEM que estar ordenada. Dividi-se a lista ao meio
e se verifica se o alvo é esse item do meio da lista
se não verifica-se se é menor ou maior que o índice central
da lista, e busca-se do meio para baixo ou para cima
de acordo com a informação
"""

def bin_search(lista,alvo):
    achou = False
    controle = 0
    indice_medio = len(lista) // 2
    tamanho = len(lista)
    passou = False

    if lista[indice_medio] == alvo:
        achou = True
    elif alvo > lista[indice_medio]:
        controle = indice_medio
        while controle < tamanho and not achou and not passou:
            if lista[controle] == alvo:
                achou = True
            else:
                if lista[controle] > alvo:
                    passou = True
                else:
                    controle = controle + 1
    else:
        controle = 0
        while controle < indice_medio and not achou and not passou:
            if lista[controle] == alvo:
                achou = True
            else:
                if lista[controle] > alvo:
                    passou = True
                else:
                    controle = controle + 1
    return achou

print('Busca binária de metades:',bin_search(lista1,4))

"""
Busca binária recursiva atualizando o centro da busca para dividir
cada vez mais. Assim economizamos ainda mais processamento
comparando com metades sempre menores
"""

def bin_search_middle(lista,esquerda,direita,alvo):
    if esquerda > direita:
        return -1
    meio = (esquerda+direita) // 2
    if lista[meio] == alvo:
        return meio
    elif lista[meio] > alvo:
        return bin_search_middle(lista,esquerda,meio-1,alvo)
    else:
        return bin_search_middle(lista,meio+1,direita,alvo)

print('Busca Binária:',bin_search_middle(lista1,0,len(lista1) -1,1))
print('Busca Binária:',bin_search_middle(lista1,0,len(lista1)-1,31))
print('Busca Binária:',bin_search_middle(lista1,0,len(lista1) -1,33))

"""
Busca binária ITERATIVA atualizando o centro da busca para dividir
cada vez mais. Assim economizamos ainda mais processamento
comparando com metades sempre menores
"""

def bin_search_it(lista,esquerda,direita,alvo):
    while esquerda <= direita:
        meio = (esquerda+direita) // 2
        if lista[meio] == alvo:
            return meio
        elif lista[meio] > alvo:
            direita = meio - 1
        else:
            esquerda = meio + 1
    return -1

print('Busca Binária Iterativa:',bin_search_it(lista1,0,len(lista1)-1,3))
print('Busca Binária Iterativa:',bin_search_it(lista1,0,len(lista1)-1,31))
print('Busca Binária Iterativa:',bin_search_it(lista1,0,len(lista1)-1,33))