Pesquisa Ternária em um vetor ordenado

Publicado por Giovanni Cândido da Silva 24/06/2009

[ Hits: 10.451 ]

Homepage: http://giovannicandido.wordpress.com

Download pesquisaternaria.txt




O algoritimo de pesquisa binária divide o vetor sucessivamente em duas partes, e utiliza a mesma
lógica porém dividindo o vetor em 3 partes.

  



Esconder código-fonte

   /**
    * Divide um vetor em 3 partes sucessivamente em busca de um elemento
    * Retorna -1 caso o elemento não exista no vetor, ou o indice do elemento
    * @param x
    * @return
    */
   public int pesquisaTer(int x){
      
      
      int meio1, meio2;
      int esq = 0;
      int dir = arranjo.length-1;
      
      do{
         
         //Calcula a primeira parte do vetor evitando estrapolação
         meio1=(dir - esq)/3 + esq;
         
         //Calcula a segunda parte do vetor evitando que 
         meio2=((dir-esq)/3)*2 + esq;
         
         //Caso o arranjo esteja em um dos meios encerra o metodo e retorna a posição
         if(x==arranjo[meio1])
            return meio1;
         if(x==arranjo[meio2])
            return meio2;
               
         //Atualiza os indices esq e dir caso nao seja encontrado o elemento
         if(x<arranjo[meio1]){
            dir=meio1-1;
         }
         if (x>arranjo[meio1] && x< arranjo[meio2]){
            esq=meio1+1;
            dir=meio2 -1;
            }
            else if(x>arranjo[meio2]){
            esq=meio2+1;
            }
         }while(esq<=dir);
      return -1;

   }

Scripts recomendados

Reconhecedor de palavras

Algoritmos para Teoria dos Números

Determinante de uma matriz de ordem 3.

Contador de caracteres, palavras e linhas de um arquivo

Planilha de cálculo para multa judicial


  

Comentários

Nenhum comentário foi encontrado.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts