A pesquisa binária é um dos muitos algoritmos de busca, ele recebe como entrada uma lista ordenada de elementos e o elemento que desejamos buscar, se o elemento buscado estiver na lista, recebemos como resposta a posição que aquele elemento se encontra, caso contrário a pesquisa retorna None. É preciso lembrar que pesquisa binária só funciona se a lista estiver ordenada, isso é necessário pois o elemento é buscado de forma ordenada dentro da lista. ex: temos uma lista de elementos dentro de um array [1,2,3,4,5,6,7,8,9,10] e queremos saber se o elemento 8 faz parte da lista, a primeira coisa que o algoritmo faz é partir a lista ao meio e verificar se o elemento é maior ou menor do que o elemento do meio, que seria 5 e no nosso exemplo ele seria maior então todos os elementos para trás seriam ignorados e a busca continuaria do numero 6 em diante.
Implementação de um algoritmo de busca binária usando Python
def pesquisa_binaria(lista, elemento):
esquerda = 0
direita = len(lista) - 1
while esquerda <= direita:
meio = (esquerda + direita) // 2
chute = lista[meio]
if chute == elemento:
return meio
elif chute > elemento:
direita = meio - 1
else:
esquerda = meio + 1
return None
Top comments (0)