estrutura de dados pesquisa binaria

Pesquisa Binária

Introdução
Trataremos do assunto relacionado à Pesquisa Binária, cujo funcionamento é ideal quando você tem o arranjo em ordem, segue o paradigma da divisão e conquista, dividindo o vetor pela metade e verificando o lado que o elemento desejado pode estar.

Conceito

A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop) é um algoritmo de busca em vetores que segue o paradigma de divisão e conquista. Ela parte do pressuposto de que o vetor está ordenado e realiza 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. Se concluirmos que o elemento está em uma das partes do vetor, repetimos o procedimento considerando apenas a parte restante: comparamos o elemento buscado com o elemento armazenado no meio dessa parte. Esse procedimento é continuamente repetido, subdividindo a parte de interesse, até encontrar o elemento ou chegar a uma parte do vetor com tamanho zero.

Busca Binária em Vetor Ordenado
• entrada: vetor vet com n elementos, ordenado: elemento elem .
• saída: n se o elemento elem ocorre em vet[n] - 1 se o elemento não se encontra no vetor
• procedimento:
– compare elem com o elemento do meio de vet
– se elem for menor, pesquise na primeira metade do vetor.
– se elem for maior, pesquise na segunda parte do vetor.
– se for igual, retorne a posição.
– continue o procedimento, subdividindo a parte de interesse, até encontrar o elemento ou chegar a uma parte do vetor com tamanho 0. int busca_bin (int n, int*