Algoritmos de Busca #3 – Busca Binária

Aproveitando o embalo, aqui vai mais um algoritmo de busca. A Busca Binária consiste em realizar sucessivas divisões do espaço de busca comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor. (Wikipedia)

Pode parecer um pouco confuso, mas esse algoritmo possui um desempenho bem melhor que, por exemplo, a busca sequencial mostrada anteriormente.

Segue, então, minha implementação em C. Como nos outros, caso o valor seja encontrado, retorna-se o índice do item no vetor. Caso contrário, retorna-se -1.

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google

Você está comentando utilizando sua conta Google. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s

Este site utiliza o Akismet para reduzir spam. Saiba como seus dados em comentários são processados.