This content originally appeared on DEV Community and was authored by Gustavo Medeiros
Introdução
Algoritmo é um conjunto de instruções que realizam uma tarefa.
Pesquisa Binária
Vamos supor que você entre no Facebook. Ao fazer isso, o Facebook precisa verificar se você tem uma conta no site. Logo, ele procura seu nome de usuário em um banco de dados. Digamos que seu usuário seja "TonyStark". O Facebook poderia começar pela letra "A" para procurar seu nome, mas faz mais sentido começar pelo meio.
Isso é um problema de busca. E todos esses casos usam um algoritmo para resolvê-lo: Pesquisa Binária.
A pesquisa binária é um algoritmo cuja entrada é uma lista ordenada de elementos. Se o elemento que você está buscando está na lista, a pesquisa binária retorna sua localização. Caso contrário, a pesquisa binária retorna None.
Nota: A pesquisa binária só funciona quando a lista está ordenada. Por exemplo, os nomes em uma agenda telefônica estão em ordem alfabética.
Vamos escrever a pesquisa binária em Python. O exemplo de código que utilizaremos aqui usa arrays. A função pesquisa_binaria recebe um array ordenado e um item. Se o item estiver no array, a função retorna sua posição. Dessa maneira, você sabe a partir de qual ponto do array deve continuar procurando. No início, o código do array segue assim:
baixo = 0
alto = len(lista) - 1
meio = (baixo + alto) // 2
chute = lista[meio]
Nota: meio será arredondado para baixo automaticamente pelo Python se (baixo + alto) não for um número par.
Se o chute for baixo, você atualizará a variável baixo proporcionalmente:
if chute < item:
baixo = meio + 1
E se o chute for muito alto, você atualizará a variável alto. Aqui está o código completo:
def pesquisa_binaria(lista, item):
baixo = 0
alto = len(lista) - 1
while baixo <= alto:
meio = (baixo + alto) // 2
chute = lista[meio]
if chute == item:
return meio
if chute > item:
alto = meio - 1
else:
baixo = meio + 1
return None
minha_lista = [1, 3, 5, 7, 9]
print(pesquisa_binaria(minha_lista, 3)) # => 1
print(pesquisa_binaria(minha_lista, -1)) # => None
Explicação
- baixo e alto acompanham a parte da lista que você está procurando;
- Enquanto ainda não chegou a um único elemento, verifique o elemento central;
- Encontre o item;
- O chute foi muito alto;
- O chute foi muito baixo;
- O item não existe;
- Vamos testá-lo;
- Lembre-se: as listas começam no índice 0. O próximo endereço tem índice 1;
- None significa nulo em Python. Ele indica que o item não foi encontrado.
Livro de referência: Para um entendimento mais profundo sobre algoritmos, recomendo o livro "Entendendo Algoritmos: Um Guia Ilustrado para Programadores e Outros Curiosos" de Aditya Y. Bhargava. Esse livro fornece explicações claras e ilustradas de diversos algoritmos, incluindo a pesquisa binária.
This content originally appeared on DEV Community and was authored by Gustavo Medeiros
Gustavo Medeiros | Sciencx (2024-09-17T22:42:33+00:00) Introdução a algoritmos: Pesquisa binária. Retrieved from https://www.scien.cx/2024/09/17/introducao-a-algoritmos-pesquisa-binaria/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.