Pesquisa linear

A pesquisa linear é o que faz quando procura um nome numa lista não ordenada: começa no topo e lê para baixo até o encontrar. É a pesquisa mais simples que existe, funciona com qualquer lista e, para listas curtas, muitas vezes é tudo o que precisa.

Barras de uma lista verificadas uma a uma desde o início, as barras verificadas esbatidas, uma linha tracejada à altura do valor procurado e a barra correspondente destacada
Barras de uma lista verificadas uma a uma desde o início, as barras verificadas esbatidas, uma linha tracejada à altura do valor procurado e a barra correspondente destacada

A ideia

Compare o valor procurado com o primeiro valor da lista. Se forem iguais, pare: o valor procurado está na posição 1. Caso contrário, compare-o com o segundo valor, depois com o terceiro, e assim por diante. Se o último valor também não corresponder, o valor procurado não está na lista. Não é preciso saber nada sobre a lista de antemão: não tem de estar ordenada, e os valores podem ser qualquer coisa que se possa comparar quanto à igualdade.

Um exemplo

Procure 4 em 5, 1, 4, 2, 8. 5 é igual a 4? Não. E 1? Não. E 4? Sim: encontrado na posição 3 após 3 comparações. Agora procure 7 na mesma lista. Cada um dos cinco valores é verificado e nenhum corresponde, por isso, após 5 comparações, a resposta é que 7 não está lá.

Quantas comparações

Encontrar um valor na posição k custa k comparações. Se o valor procurado tiver a mesma probabilidade de estar em qualquer posição, são (n + 1)/2 comparações em média: 20,5 para 40 valores. Um valor em falta custa sempre n, porque só após a última comparação é certo que nenhum valor correspondeu. Assim, o custo cresce em proporção ao comprimento da lista, o que se escreve O(n).

Pesquisas mais rápidas precisam de ordem

A pesquisa linear não pode saltar nada, porque numa lista não ordenada qualquer valor pode estar em qualquer lado. Quando a lista está ordenada, uma comparação diz mais do que igual ou não: diz de que lado está o valor procurado. A pesquisa binária usa isso para dividir a lista ao meio a cada passo e precisa de cerca de log₂ n comparações, no máximo 6 para 40 valores. Mas ordenar também leva tempo, por isso, para uma lista pesquisada só uma vez, a pesquisa linear é muitas vezes a melhor escolha.

Pequenas melhorias

Uma versão com sentinela coloca o valor procurado no fim da lista antes de pesquisar, para que o ciclo só tenha de testar se há correspondência e não também o fim da lista. Avançar um valor uma posição, ou passá-lo para a frente, sempre que é encontrado torna os valores pesquisados com frequência mais baratos com o tempo. Nenhuma das duas altera o pior caso de n comparações.

Experimente

Abra a aplicação, escolha um valor em Procurar e prima Avançar. A linha tracejada mostra a altura do valor procurado, cada valor é destacado enquanto é verificado e esbate-se quando é excluído, e uma correspondência fica verde. Procure um valor que não está na lista para ver uma passagem completa, ou desative «Parar na primeira correspondência» e escolha Poucos valores distintos para encontrar várias correspondências.

Perguntas frequentes

Qual é a complexidade temporal da pesquisa linear?

O(n) no pior caso e no caso médio, e O(1) no melhor caso, quando o valor procurado é o primeiro. Não precisa de memória adicional.

Qual é a diferença entre pesquisa linear e pesquisa binária?

A pesquisa linear verifica cada valor por ordem e funciona com qualquer lista. A pesquisa binária só funciona numa lista ordenada, mas divide ao meio, a cada passo, a parte que pode conter o valor procurado, por isso precisa de cerca de log₂ n comparações em vez de até n.

A pesquisa linear precisa de uma lista ordenada?

Não. Essa é a sua principal vantagem. Numa lista ordenada, pode parar assim que passa a posição onde o valor procurado estaria, mas continua mais lenta do que a pesquisa binária.

Onde se usa a pesquisa linear?

Em todo o lado onde as listas são curtas ou não ordenadas: encontrar um elemento num pequeno array, percorrer um ficheiro ou um fluxo que só se pode ler por ordem, ou verificar uma condição em cada elemento. Muitas funções de biblioteca, como indexOf em JavaScript e list.index em Python, são pesquisas lineares.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Experimentar a pesquisa linear