11

Como posso realizar uma busca binária numa lista encadeada simples com cabeça? Também se é possível fazer isso, se existe algum método especial. No EP não posso contar de antemão a quantidade de elementos dessa lista, tenho que fazer a busca e inserir uma célula entre q->prox e p.

5
  • A lista está ordenada, importo ele de um arquivo texto, porém a quantidade de elementos "não sei de antemão". Commented 26/11/2015 às 3:03
  • E você pode contar os elementos ? Commented 26/11/2015 às 3:05
  • 1
    Não entendi o motivo dessa pergunta ter sido classificada como ampla demais.
    – cantoni
    Commented 26/11/2015 às 12:56
  • 2
    O que significam "EP", p e q->prox, dentro do problema?
    – Gabe
    Commented 1/12/2015 às 19:06
  • 1
    @MarcelodeSousa, acho que vale a pena você dar uma melhorada na sua pergunta. Você já teve 10 votos com ela assim. Se você fizer isso, sua pergunta tem a chance de ser reaberta e ganhar mais atenção da comunidade, com mais respostas e discussão em cima desse interessante tema.
    – cantoni
    Commented 9/12/2015 às 18:05

2 Respostas 2

11

É possível aplicar a Busca Binária numa lista encadeada, entretanto, você perderá a principal razão para usar a Busca Binária, o fator dela ter complexidade O(log n).

O fato é que buscas binárias aplicadas em arrays são eficientes, pois os elementos de um array são alocados na memória de maneira contígua, o que torna o acesso a qualquer elemento uma operação trivial, O(1).

Por outro lado, numa lista encadeada não há garantias de que os elementos serão alocados de maneira contígua e, mesmo que estivessem, não há como acessá-los em tempo O(1). Dessa maneira, para encontrar o meio da lista, é preciso desenlvolver um algoritmo que terá que visitar nós até encontrar o meio. Essa operação já torna o algoritmo mais lento. O pior caso de uma busca binária em uma lista encadeada é O(n log n).

Por causa disso, buscas sequenciais em listas encadeadas tendem a ser mais rápidas, já que O(n) < O(n log n). Ver atualização mais embaixo para casos onde pode valer a pena usar busca binária numa lista encadeada.

Sobre o algoritmo, esse parece interessante: http://www.algo-faq.com/Linked-List/Find-the-middle-node-of-a-linked-list.php

O desafio, se comparado com os arrays, é determinar o meio da lista. Para isso, o algoritmo acima utiliza uma abordagem diferente que não requer saber o tamanho da lista previamente.

Este mesmo algoritmo está descrito nesse artigo: http://www.ijcsit.com/docs/Volume%205/vol5issue02/ijcsit20140502215.pdf

Já que se trata de um exercício, eu iria pelo caminho citado acima.

Atualização

Existem casos onde pode fazer sentido o uso da busca binária em uma lista encadeada, explico.

Suponha que a tarefa de fazer a comparação seja custosa. Nesse caso, o algoritmo de busca binária pode fazer sentido, pois são feitas O(log n) comparações. Na parte O(n) não é feita comparação, mas apenas percorre-se a lista para encontrar o meio.

Por outro lado, se o algoritmo for busca sequencial então, pra cada item, a comparação é realizada. O que pode se tornar algo mais custoso se comparado com o cenário da busca binária.

3

Considerando que se possa obter a quantidade de elementos, você pode descobrir qual é a metade da lista. Com isso você teria que percorrer da cabeça da lista até o meio e comparar o valor desejado com o nó do meio, caso seja maior deverá considerar a posição do meio o inicio da lista e encontrar o meio do novo início até o fim, ou o contrário caso seja menor. O problema é que você não tem ganho nenhum de performance.

Abaixo um código que não testei, mas creio que deve ser próximo do que precisa.

celula *buscaR (int qnt, int x, celula *ini)
{
   if (ini->prox == NULL) 
      return NULL;
   p = ini->prox;
   int count = 0;
   while (p != NULL && p->conteudo != x) {
        p = p->prox;
        if(count++ == qnt/2){
            if (p->prox->conteudo == x) 
              return p->prox;
            else{
                if(p->prox->conteudo > x){
                    return buscaR (qnt/2, x, p->prox);      
                }else{
                    return buscaR (qnt/2, x, ini->prox);
                }
            }
        }
   }
}

Atualização

Se considerarmos o trecho "No EP não posso contar de antemão a quantidade de elementos dessa lista" a resposta é:

Não será possível aplicar uma solução já que é primordial na busca binária termos quantidade de elementos da lista.

7
  • No enunciado do problema não diz que sim nem que não, se poderíamos contar os elementos, não há uma restrição aparente, qdo perguntaram ao professor ele deu a entender que deveríamos pesquisar sobre esta questão, se era possível ou não. Commented 26/11/2015 às 3:14
  • Uma lista ligada não se beneficia de busca binária - no seu código mesmo você faz uma busca linear pela lista procurando o elemento - (e tem um outro erro: você não retorna a posição quando encontra o elemento - o caso em que p->conteudo == x no while)
    – jsbueno
    Commented 26/11/2015 às 12:22
  • Eu informei no fim do texto que não tem ganho performático. A razão de se aplicar uma varredura binária em uma lista encadeada ordenada é porque é um exercício, não tem sentido e ganho nenhum considerando a pesquisa sequencial para encontrar o meio da lista. Commented 26/11/2015 às 12:56
  • Eventualmente pode ter um ganho. Veja a atualização da minha resposta.
    – cantoni
    Commented 26/11/2015 às 13:01
  • 1
    "No EP não posso contar de antemão a quantidade de elementos dessa lista"
    – Largato
    Commented 26/11/2015 às 23:50

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .