Algoritmos de Busca – Python

Busca Linear

# Busca Linear percorrer a Lista toda e retornar TRUE ou index

# Busca Linear com "in"
Lista = [6, 5, 2, 3]
5 in Lista    # Retornará TRUE
4 in Lista    # Retornará FALSE 

# Busca Linear com "index()"
Lista = [6, 5, 2, 3] 
Lista.index(5)    # Retornará 1, ou seja, 2º posição
Lista.index(4)    # Retornará ERROR

Busca Binária

Busca Binária para listas ordenadas

# Busca Binária (Lista com elementos ordenados)
Lista = [16, 37, 10, 56, 5, 12, 13, 41, 43]
Lista.sort()    # Ordenar Lista
# Função Busca Binária
def busca_binaria(lista, x, inicio, fim):
    meio = (inicio + fim) // 2
    if x == lista[meio]:
        return meio
    if x < lista[meio]:
        return busca_binaria(lista, x, inicio, meio-1)
    if x > lista[meio]:
        return busca_binaria(lista, x, meio+1, fim)

print(Lista)
buscar_elemento = 12
ultima_posicao=len(Lista)-1
print(
    busca_binaria(Lista, buscar_elemento, 0, ultima_posicao)
    )