Busca linear: procurar do começo ao fim

Conferir um por um

Quando você procura uma chave perdida na bolsa, faz uma busca linear: enfia a mão e vai tateando um objeto de cada vez até encontrar. Quando confere se um nome está numa lista bagunçada, corre o dedo de cima a baixo. Esse método de olhar item por item, na ordem em que eles aparecem, é a busca linear, e é o jeito mais natural e honesto de procurar. Em programação, ela é um laço que percorre a coleção comparando cada item com o alvo. Se um item bate, achou, e o laço para com o interromper que você aprendeu no módulo de controle de laços. Se o laço chega ao fim sem nenhum acerto, a conclusão é que o item não está lá.

lista <- [40, 15, 8, 23, 4, 16]
procurado <- 23
achou <- falso
posicao <- 0
para cada item em lista faça
  se item = procurado então
    achou <- verdadeiro
    interrompa
  fim
  posicao <- posicao + 1
fim
se achou então
  escreva("Encontrado na posição ", posicao)
senão
  escreva("Não está na lista")
fim

A busca linear percorre até achar o 23 (na posição 3) e para. Repare que a lista nem precisa estar em ordem.

A virtude e o custo da busca linear

A grande virtude da busca linear é a universalidade: ela funciona em qualquer coleção, não importa se está ordenada, embaralhada ou em que formato. Isso a torna a escolha certa quando os dados estão fora de ordem e você não quer ou não pode ordená-los antes. O custo, porém, cresce com o tamanho. No melhor caso, o item procurado é o primeiro, e uma comparação basta. No pior caso, ele está no fim ou não existe, e você precisa conferir todos os itens. Em média, examina metade. Para uma lista de dez itens, isso é rápido; para uma de dez milhões, uma única busca pode custar dez milhões de comparações, e se o programa faz muitas buscas, o peso soma. Essa relação entre tamanho e esforço é a semente do módulo de eficiência, e é o que motiva a busca binária da próxima aula.

lista <- [3, 7, 1, 9, 5]
// busca linear pelo 9, contando cada comparação
// compara 3? não. 7? não. 1? não. 9? sim!

Quando a busca linear é a escolha certa

Apesar de simples, a busca linear não é uma técnica inferior a ser abandonada; ela é a ferramenta certa em várias situações. Quando a lista é pequena, a diferença de velocidade para métodos mais espertos é irrelevante, e a simplicidade compensa. Quando os dados não estão ordenados e você faria só uma ou duas buscas, ordenar primeiro daria mais trabalho do que economizaria. E quando a estrutura não permite pular para o meio (algumas formas de guardar dados só deixam avançar de um em um), a busca linear é a única opção. O erro não é usar busca linear, é usá-la em listas enormes que você consulta o tempo todo sem perceber que existe um caminho muito mais rápido quando os dados estão em ordem, que é justamente o que vem a seguir.