Busca binária

De Wiki DAINF
(Diferença entre revisões)
(Nova página: A ser editado...)
 
 
(Uma edição intermediária de um usuário não apresentada)
Linha 1: Linha 1:
−
A ser editado...
+
[[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==
 +
 +
* FEOFILOFF, Paulo. Projeto de Algoritmos: Busca binaria (versao simplificada). Disponível em: <http://www.ime.usp.br/~pf/algoritmos/aulas/bubi2.html>. Acesso em: 24 nov. 2008
 +
* RICARTE, Ivan L. M. Busca binária. Disponível em: <http://www.dca.fee.unicamp.br/cursos/EA876/apostila/HTML/node20.html>. Acesso em: 24 nov. 2008
 +
* Wikipedia, a enciclopédia livre. Pesquisa Binária. Disponível em: <http://pt.wikipedia.org/wiki/Busca_Bin%C3%A1ria>. Acesso em: 24 nov. 2008

Edição atual tal como 19h18min de 1 de dezembro de 2008

Funcionamento da busca binária para a procura do número 3 no vetor dos números de 1 a 9.

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();
}

Referências

Obtida de "http://dainf.ct.utfpr.edu.br/wiki/index.php?title=Busca_bin%C3%A1ria&oldid=869"
Ferramentas pessoais