Comparações
Correspondências
Por verificar

  • Valor procurado
  • Comparados
  • Excluídos
  • Encontrados

Mais sobre a pesquisa linear

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

  1. Escolha o valor a procurar, o número de barras e a ordem inicial. Ou escreva os seus próprios números.
  2. 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.
  3. 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