Algoritmos de Busca #4 – Busca Direta Transformada

Padrão


Temos aqui outro algoritmo de busca, chamado de Busca Direta Transformada. Dos algoritmos de busca apresentados até agora, este é o que possui o melhor desempenho.

Segue a implementação do algoritmo em C:

int buscaDiretaTransformada(int *vetor, int chave, int tamanho)
{
   int kmenor = vetor[0];
   int kmaior = vetor[tamanho - 1];
   int den = kmaior - kmenor;
   int cte1 = (kmaior - (tamanho - 1) * kmenor) / den;
   int cte2 = (tamanho - 2) / den;

   int end = cte1 + chave * cte2;

   if(chave != vetor[end])
   {
      if(chave < vetor[end])
         while(end > 0 && chave < vetor[end])
            end--;
      else
         while(end < tamanho - 1 && chave > vetor[end])
            end++;
   }

   if(end >= 0 && end < tamanho && chave == vetor[end])
      return end;

   return -1;
}


Deixe uma resposta