Busca binária
A busca binária é um algoritmo de busca em vetores mais eficiente que a busca linear. Seu funcionamento, porém, é mais complexo.
Descrição
A busca binária, primeiramente, nomeia o vetor "0" como sendo o vetor inferior e o vetor "N-1" (N é o número de elementos do vetor) como sendo o vetor superior. A média aritmética entre os números de posição do vetor inferior e do vetor superior dá como resultado a posição do vetor do meio (lembrando que, por serem números inteiros, sua média aritmética retorna um valor também inteiro; por exemplo, se a média for 4,5, o valor retornado é 4). Se o vetor do meio for igual ao número procurado, a busca é cessada e a busca retorna o valor do vetor. Se o vetor do meio não for igual ao número procurado, o programa confere se o vetor procurado é maior ou menor que o atual vetor do meio. Se for menor, o vetor superior é mudado para a posição “meio-1”. Se for maior, o vetor inferior muda para a posição “meio+1”. Assim, é calculada a nova média, que dá a posição do novo vetor do meio. O programa compara novamente este vetor com o do meio, enfim, realizando as mesmas operações citadas anteriormente. Se o programa chegar ao ponto em que as posições inferior e superior se igualam, ele retorna “-1”, o que indica que não existe o número procurado no vetor.
Implementação em C
#include <stdio.h>
#include <conio.h>
int PesquisaBinaria ( int k[], int chave , int N)
{
int inf,sup,meio;
inf=0;
sup=N-1;
while (inf<=sup)
{
meio=(inf+sup)/2;
if (chave==k[meio])
return meio;
else if (chave<k[meio])
sup=meio-1;
else
inf=meio+1;
}
return -1;
}
int main (){
int c, i, v[9]={1, 2, 3, 4, 5, 6, 7, 8, 9};
printf ("Digite numero procurado: ");
scanf ("%d", &i);
c=PesquisaBinaria (v, i, 9);
if (c==-1)
printf ("O vetor nao contem o numero procurado");
else
printf ("O numero encontra-se no vetor %d", c);
getch();
}
