[Resolvido] Busca Binária na Lista Encadeada

[_Alexandre_ 0]

[Linguagem utilizada: C++]

Meu professor de Estrutura de Dados passou duas questões para resolvermos, que são:

 

1) Realizar a ordenação de uma lista encadeada (simples ou dupla).

2) Realizar busca binária na lista ordenada

Obs: não usar vetor!

 

Bom, a 1ª resolvi tranquilo, como segue o código abaixo:

 

   int aux;
   for (NodePtr p1 = L.first(); p1 != NULL; p1 = L.next(p1)) 
      for (NodePtr p2 = L.next(p1); p2 != NULL; p2 = L.next(p2))
         if (L.retrieve(p1) > L.retrieve(p2))
         {
            aux = L.retrieve(p1);
            L.setItem(p1, L.retrieve(p2));
            L.setItem(p2, aux);
         } 

// L.first() - retorna o 1º nodo da lista; 
// L.next(apontador) - retorna o proximo item do apontador
// L.retrieve(apontador) - retorna o item contido no endereço do apontador
// L.setItem(apontador, L.retrieve(p2)) - atrubui ao apontador o item passado 

Porém, não consigo imaginar como fazer a segunda. Sei que um código para um vetor seria tipo assim:

 

   int meio, esq, dir; // esq = esquerda; dir = direita;
   esq = 1;
   dir = size; // size é o tamanho(nº de elementos) da lista

   while (esq < dir) 
   {
      meio = (esq + dir)/2;
      if (L[meio] == n)
         return meio;
      else
         if (L[meio] < n)
            esq = meio + 1;
         else 
            dir = meio - 1;
   }

A lógica das duas (tanto vetor quanto lista) é ir dividindo as partes ao meio e ver se o item está na posição do meio, mas como saber o meio de uma lista? não existe essa possibilida sem transformá-la em um vetor. Então, gostaria de que, se possível, me ajudassem a entender como fazer essa busca binária na lista, lembrando que não quero o código pronto, quero entender a lógica e colocar a mão na massa.

 

Desde já, muito Obrigado.

[VictorCacciari 42]

A busca binária só funciona com estruturas de acesso aleatório.

Uma lista encadeada é uma lista de acesso sequêncial...

 

Pode-se simular o acesso aleatório em uma estrutura de acesso sequêncial, e então fazer a busca binária sobre essa simulação, mas o desempenho fica ridiculo...

Você precisa de duas funções:

No* meio_da_lista(Lista* l);
void divide_lista(Lista* l, Lista* primeira_metade, Lista* segunda_metade);

[guidjos 65]

Seu professor mandou mesmo fazer busca binária em lista encadeada? Não faz o menor sentido fazer isso.

[_Alexandre_ 0]

Olá pessoal,

 

andei um pouco sumiso, por isso demorei a responder), mas meu professor pediu isso sim (e até caiu na prova), mas é para que entendesse-mos como funcionaria esse tipo de busca na Lista e que não tem vantagem nenhuma fazer isso, mas pelo contrário, é muito pior. Mas foi só para introduzir a matéria de Árvore, mas que graças a Deus que consegui fazer essa questão, pois contribuiu para que eu fechasse a prova.

 

o código usado foi esse:

 

int esq, dir, meio, n;
               esq = 1;
               dir = L.length();
               cout <<"digite o Número para a Busca"<<endl;
               cin >> n;
               NodePtr p;
               bool achei;
               achei = false;             
               while(esq <= dir) 
               {                   
                   p = L.first();
                   meio = (esq + dir)/2;    
                   for (int i = 1; i < meio; i++)
                       p = L.next(p);   // p = p->prox;                        
                   if (n == L.retrieve(p))   
                   {                
                      achei = true;
                      break; // motivo: 1º pq já achou, e 2º pq se não sair vair dar Loop infinito
                   }
                   else
                      if (L.retrieve(p) < n)
                         esq = meio + 1;
                      else
                          dir = meio - 1;                                                                         
               }
               system ("CLS");
               if (achei == false)
                   cout <<"Numero não encontrado!"<< endl;                   
               else
                   cout <<"Numero [ "<< L.retrieve(p) <<" ] encontrado!"<< endl;
               system ("PAUSE");

Valew pessoal.