Algoritmos de Busca #3 – Busca Binária

Padrão

Aproveitando o embalo, aqui vai mais um algoritmo de busca. A Busca Binária consiste em realizar 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. (Wikipedia)

Pode parecer um pouco confuso, mas esse algoritmo possui um desempenho bem melhor que, por exemplo, a busca sequencial mostrada anteriormente.

Segue, então, minha implementação em C. Como nos outros, caso o valor seja encontrado, retorna-se o índice do item no vetor. Caso contrário, retorna-se -1.

int buscaBinaria(int *vetor, int chave, const int TAMANHO)
{
   int linf = 0;
   int lsup = TAMANHO - 1;
   int i = (linf + lsup) / 2;

   while(lsup >= linf && chave != vetor[i])
   {
      if(chave < vetor[i])
         lsup = i - 1;
      else
         if(chave > vetor[i])
            linf = i + 1;
      i = (linf + lsup) / 2;
   }

   if(lsup >= linf)
      return i;
   else
      return -1;
}

Deixe uma resposta