Pesquisa binária

Busca Binaria

- Utilizada em vetores ordenados

- Teste do elemento buscado com o elemento localizado no meio do vetor

- Se o elemento for menor – sabemos que se existir o elemento pesquisado ele estará na 1º parte do vetor, se for maior estará na 2º parte do vetor, se for igual achamos o elemento.

- O procedimento é continuamente repetido, subdividindo a parte de interesse, ate encontrar o elemento ou chegar a uma parte do vetor com tamanho zero

Exemplo do procedimento

Int busca_bin ( int n, int* vet, int elem)

{

Int ini = 0;

Int fim = n-1;

Int meio;

while(ini<=fim){

meio=(ini+fim)/2;

if(elem <vet[meio])

fim=meio-1;

else if(elem > vet[meio])

ini=meio+1;

else

return meio;

}

return -1;

0 }

A cada divisão a parte considerada na busca é dividida pela metade.

A pior pesquisa caracteriza-se pela situação do elemento não estar presente no vetor.

Busca Binaria

- Utilizada em vetores ordenados

- Teste do elemento buscado com o elemento localizado no meio do vetor

- Se o elemento for menor – sabemos que se existir o elemento pesquisado ele estará na 1º parte do vetor, se for maior estará na 2º parte do vetor, se for igual achamos o elemento.

- O procedimento é continuamente repetido, subdividindo a parte de interesse, ate encontrar o elemento ou chegar a uma parte do vetor com tamanho zero

Exemplo do procedimento

Int busca_bin ( int n, int* vet, int elem)

{

Int ini = 0;

Int fim = n-1;

Int meio;

while(ini<=fim){

meio=(ini+fim)/2;

if(elem <vet[meio])

fim=meio-1;

else if(elem > vet[meio])

ini=meio+1;

else

return meio;

}

return -1;

0 }

A cada divisão a parte considerada na busca é dividida pela metade.

A pior pesquisa caracteriza-se pela situação do elemento não estar presente no vetor.