- Valor procurado
- Comparados
- Excluídos
- Encontrados
Pesquisa linear
A pesquisa linear é a forma mais simples de encontrar um valor: começar no início e verificar cada valor à vez até ele aparecer. Funciona com qualquer lista, ordenada ou não. Escolha o valor a procurar, reproduza a pesquisa ou avance uma comparação de cada vez, e veja como o custo depende de onde o valor está, ou de se está lá de todo. Prima Reproduzir para ver a pesquisa, ou Avançar e Recuar para ir uma comparação de cada vez. Arraste a barra de passos para saltar para qualquer ponto. A linha tracejada marca o valor procurado. Escolha o valor, quantas barras, como começam, ou escreva os seus próprios números. Desative «Parar na primeira correspondência» para encontrar todas as correspondências. Com o quadro selecionado, as setas avançam e recuam, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.
Como funciona
- Escolha o valor a procurar, o número de barras e a ordem inicial. Ou escreva os seus próprios números.
- Prima Reproduzir, ou use Avançar e Recuar para ir uma comparação de cada vez. Arraste a barra de passos para saltar para qualquer ponto da pesquisa.
- Desative «Parar na primeira correspondência» para verificar cada valor e encontrar todas as correspondências.
Como funciona a pesquisa linear
Compare o primeiro valor com o valor procurado. Se forem iguais, terminou. Se não, passe ao segundo valor, depois ao terceiro, e assim por diante. Se chegar ao fim da lista sem uma correspondência, o valor procurado não está na lista. Não há nada a preparar: a lista não precisa de estar ordenada.
Quantas comparações
Um valor na posição k é encontrado após k comparações. O melhor caso é uma comparação, quando o valor procurado é o primeiro. O pior caso é n, quando é o último ou não está, porque só depois de verificar todos os valores pode ter a certeza de que não está lá. Em média, para um valor que está na lista, são precisas cerca de (n + 1)/2. Numa lista ordenada, a pesquisa binária faz muito melhor: cerca de log₂ n comparações, 6 em vez de até 40 para 40 valores.
Perguntas frequentes
Como funciona a pesquisa linear?
Verifica os valores de uma lista um a um, do primeiro ao último, até encontrar o valor procurado ou ficar sem valores. Também se chama pesquisa sequencial.
Qual é a complexidade temporal da pesquisa linear?
O(n): no pior caso, quando o valor procurado é o último ou não está, compara-o com todos os n valores. Em média, para um valor que está na lista, são precisas cerca de (n + 1)/2 comparações.
Quando é a pesquisa linear uma boa escolha?
Para listas curtas, para listas não ordenadas pesquisadas apenas uma ou duas vezes, e para dados que só se podem ler por ordem, como um fluxo. Ordenar primeiro para poder usar a pesquisa binária só compensa se pesquisar muitas vezes.
Porque é que um valor em falta custa mais?
Porque nada diz à pesquisa linear para parar mais cedo. Uma correspondência só pode ser excluída verificando todos os valores, por isso um valor que não está na lista custa sempre n comparações.
Os meus números são enviados para algum lado?
Não. A pesquisa corre no seu navegador, e as suas últimas definições ficam no armazenamento local deste navegador.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Ir para o editor