Introdução a pesquisa em listas

Um problema comum consiste em procurar um elemento $x$ numa lista $L$. Existem várias situações onde este tipo de primitiva é útil. Veremos como podemos resolver este problema.

Pesquisa linear

Existe uma solução óbvia para este problema que consiste em percorrer a lista de valores comparando $x$ com os vários valores da lista $L$ até encontrar um igual ou percorrer a lista na sua totalidade.

É fácil de ver que a complexidade temporal deste método é $O(N)$.

Pesquisa binária

Se admitirmos que a lista onde estamos a procurar está ordenada, podemos melhorar a pesquisa da secção anterior. O método é análogo a como procuramos alguém numa lista de nomes ordenada (por exemplo, numa lista telefónica).

Como o artigo explica, este algoritmo permite encontrar elementos com uma complexidade temporal de apenas $O(\log(N))$, que, como se pode ver no artigo de análise de algoritmos, é uma grande diferença!

Aplicações

Terminamos com uma aplicação simples, mas não trivial do algoritmo.

Veremos no futuro como aplicar este conceito de uma forma mais genérica para resolver diferentes tipos de problema. Na verdade, este tipo de raciocínio é muito recorrente em problemas de concurso.