Busca binária
(Nova página: A ser editado...) |
|||
Linha 1: | Linha 1: | ||
− | A | + | [[Image:Busca_Bin%C3%A1ria.jpg|thumb|Funcionamento da busca binária para a procura do número 3 no vetor dos números de 1 a 9.|right|250px]] |
+ | |||
+ | 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== | ||
+ | <pre> | ||
+ | #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(); | ||
+ | } | ||
+ | </pre> | ||
+ | |||
+ | ==Referências== | ||
+ | * http://pt.wikipedia.org/wiki/Busca_Bin%C3%A1ria | ||
+ | * http://www.dca.fee.unicamp.br/cursos/EA876/apostila/HTML/node20.html | ||
+ | * http://www.ime.usp.br/~pf/algoritmos/aulas/bubi2.html |
Edição de 19h55min de 24 de novembro de 2008
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(); }