Pesquisa binária

algoritmo de busca

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.

Pesquisa binária
classe Algoritmo de busca
estrutura de dados Array
complexidade caso médio
complexidade melhor caso
complexidade de espaços pior caso
otimo Sim
espaço
Algoritmos

Análise de Complexidade

editar

A complexidade desse algoritmo é da ordem de  [1], em que   é o tamanho do vetor de busca. Apresenta-se mais eficiente que a Busca linear cuja ordem é  [2].

Procedimento

editar

Dado uma lista   de   elementos com os valores  ,  ,  ,  ,  ordenada de tal modo que  , e um valor para pesquisa  , a seguinte rotina usa pesquisa binária para achar o índice de   em  .

  1. Defina   para 0 e   para  
  2. Se   a pesquisa termina sem sucesso
  3. Defina  (o índice do meio da lista) para   arredondado
  4. Se  , defina   para   e volte ao segundo passo
  5. Se  , defina   para   e volte ao segundo passo.
  6. Se  , a pesquisa está feita, o índice de   é  

Implementações

editar

Pseudo-Código

editar

Um pseudo-código recursivo para esse algoritmo, dados V o vetor com elementos comparáveis e e o elemento que se deseja encontrar:

BUSCA-BINÁRIA(V[], início, fim, e)
    i recebe o índice do meio entre início e fim
    se (v[i] = e) entao
        devolva o índice i   # elemento e encontrado
    fimse
    se (inicio = fim) entao
        não encontrou o elemento procurado
    senão
       se (V[i] vem antes de e) então
          faça a BUSCA-BINÁRIA(V, i+1, fim, e)
       senão
          faça a BUSCA-BINÁRIA(V, inicio, i-1, e)
       fimse
    fimse

Código em C

editar
//Implementação Iterativa:

int PesquisaBinaria (int vet[], int chave, int Tam)
{
     int inf = 0;     // limite inferior (o primeiro índice de vetor em C é zero          )
     int sup = Tam-1; // limite superior (termina em um número a menos. 0 a 9 são 10 números)
     int meio;
     while (inf <= sup)
     {
          meio = (inf + sup)/2;
          if (chave == vet[meio])
               return meio;
          if (chave < vet[meio])
               sup = meio-1;
          else
               inf = meio+1;
     }
     return -1;   // não encontrado
}

//Implementação Recursiva:

// x => chave | v[] => vetor ordenado | e => limite inferior (esquerda) | d => limite superior (direita)
int PesquisaBinaria (int x, int v[], int e, int d)
{
 int meio = (e + d)/2;
 if (v[meio] == x)
    return meio;
 if (e >= d)
    return -1; // não encontrado
 else
     if (v[meio] < x)
        return PesquisaBinaria(x, v, meio+1,      d);
     else
        return PesquisaBinaria(x, v,      e, meio-1);
}

Obs: A linguagem C fornece a função bsearch[3] na sua biblioteca padrão.

Ver também

editar

Referências

  1. Felipe, Henrique (6 de setembro de 2017). «A Busca Binária». Blog Cyberini. Consultado em 8 de julho de 2018 
  2. Felipe, Henrique (14 de setembro de 2017). «Busca Linear». Blog Cyberini. Consultado em 8 de julho de 2018 
  3. «bsearch(3): binary search of sorted array - Linux man page». linux.die.net (em inglês). Consultado em 8 de julho de 2018 

Ligações externas

editar