Algoritmos de Busca #4 – Busca Direta Transformada

bb_bid = “1661096”;
bb_lang = “pt-BR”;
bb_keywords = ” ‘names’))); ?>”;
bb_name = “custom”;
bb_limit = “7”;
bb_format = “bbc”;

http://static.boo-box.com/javascripts/embed.js

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

http://pagead2.googlesyndication.com/pagead/show_ads.js

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google

Você está comentando utilizando sua conta Google. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s

Este site utiliza o Akismet para reduzir spam. Saiba como seus dados em comentários são processados.