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)<br />
{<br />
   int linf = 0;<br />
   int lsup = TAMANHO - 1;<br />
   int i = (linf + lsup) / 2;</p>
<p>   while(lsup &gt;= linf &amp;&amp; chave != vetor[i])<br />
   {<br />
      if(chave &lt; vetor[i])<br />
         lsup = i - 1;<br />
      else<br />
         if(chave &gt; vetor[i])<br />
            linf = i + 1;<br />
      i = (linf + lsup) / 2;<br />
   }</p>
<p>   if(lsup &gt;= linf)<br />
      return i;<br />
   else<br />
      return -1;<br />
}