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
.
2 Respostas
É 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.
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.
-
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)– jsbuenoCommented 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.– cantoniCommented 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
p
eq->prox
, dentro do problema?