Procurando na lista: tem ou não tem?

A pergunta mais feita da computação

Pense em quantas vezes por dia algo é procurado dentro de uma lista: seu CPF na lista da vacina, o nome do filme no catálogo, o produto no estoque, o contato na agenda do celular. Toda essa procura, lá no fundo, começa com o algoritmo desta aula: a busca linear. Ela pega o valor procurado e caminha pela lista comparando caixa por caixa, exatamente como o segurança confere a lista de convidados na porta da festa: dedo no papel, nome por nome, de cima para baixo, até achar ou até a lista acabar.

A moldura você já tem: é o percurso da aula 3, com um SE do módulo 8 no miolo. A novidade está em duas decisões de projeto. Primeira: o que responder? Um simples “tem ou não tem” serve às vezes, mas guardar a POSIÇÃO do achado responde as duas coisas de uma vez (se posicao é 2, o valor está lá; e está na caixa 2). Segunda: como dizer “não achei” sem mentir? A resposta é o valor sentinela -1, um número que nenhum índice de verdade usa, já que índices começam no zero e nunca são negativos.

convidados <- ["Ana", "Bruno", "Carla", "Davi"]
procurado <- "Carla"
posicao <- -1
para i de 0 até tamanho(convidados) - 1 faça
  se convidados[i] = procurado então
    posicao <- i
  fim
fim
se posicao = -1 então
  escreva("Não está na lista")
senão
  escreva("Encontrado na posição " + posicao)   // Encontrado na posição 2
fim

A busca completa: percorre, compara, guarda a posição e responde com honestidade.

Parar quando achar: a elegância de não trabalhar à toa

O algoritmo acima funciona, mas tem um desperdício escondido: mesmo achando a Carla na caixa 2, ele continua conferindo o Davi. Em quatro convidados, ninguém percebe. Numa lista de 1 milhão de clientes em que o procurado está na caixa 10, seriam 999.990 comparações jogadas fora. A correção é declarar vitória e encerrar: assim que lista[i] for igual ao procurado, guarde a posição e saia do laço. Em pseudocódigo, usamos o comando pare, que interrompe o laço na hora; as linguagens reais têm o equivalente (break).

para i de 0 até tamanho(convidados) - 1 faça
  se convidados[i] = procurado então
    posicao <- i
    pare              // achou: não há motivo para continuar
  fim
fim

Com o pare, a busca faz só o trabalho necessário: no melhor caso, uma comparação.

As afirmações do jogo escondem uma ideia que vale destacar: a busca tem melhor caso, pior caso e caso médio. Achar na primeira caixa custa 1 comparação; não achar custa tamanho(lista) comparações. Quando a lista está ORDENADA, existe uma estratégia radicalmente melhor, a busca binária, que abre a lista no meio como quem procura num dicionário e descarta metade a cada passo. Ela não é assunto deste curso introdutório, mas fica o gostinho: com 1 milhão de itens ordenados, ela acha qualquer um em cerca de 20 passos.

O fecho do módulo: quatro ferramentas no cinto

Faça o balanço do módulo. Você aprendeu o que é uma lista (caixas numeradas sob um nome), gravou a contagem do zero (primeira caixa no índice 0, última no tamanho menos 1), casou o laço PARA com o índice para percorrer tudo e aplicou o percurso nos quatro clássicos: somar, tirar média, achar o maior e buscar. Não é exagero dizer que uma fatia enorme dos programas do mundo real é feita desses movimentos combinados: o extrato do banco soma, o placar do campeonato acha o maior, o campo de pesquisa busca.

• Percorrer: para i de 0 até tamanho(lista) - 1 faça ... fim.
• Somar: acumulador que nasce 0 e cresce com lista[i] a cada volta.
• Maior: campeão provisório que nasce lista[0] e defende o posto caixa a caixa.
• Buscar: comparar caixa a caixa, guardar a posição, parar ao achar, responder -1 se não achar.

No módulo 12, esses algoritmos ganham nome próprio e viram peças reutilizáveis: as funções. Você vai embrulhar a busca desta aula numa máquina chamada buscar(lista, valor) e usá-la em qualquer programa com uma linha, sem copiar e colar o laço nunca mais.