Algoritmos

Busca linear: o que é e como funciona

Capa do artigo Busca linear: o que é e como funciona
Leitura com foco

Entenda o contexto.
Leve para a prática.

Neste artigo
  1. Como funciona a busca linear?
  2. Exemplo de busca linear passo a passo
  3. Busca linear em Python, PHP, C e JavaScript
  4. Quantas comparações a busca linear faz?
  5. Aí você pergunta: o que é esse n?
  6. Quais medidas são usadas para explicar o Big O?
  7. Aí você pergunta: existe uma busca mais rápida do que a linear?
  8. Preciso escrever a busca linear toda vez?
  9. Quais são os erros mais comuns na busca linear?
  10. Agora é com você!

Busca linear é um algoritmo que procura um valor olhando os elementos um por um, do primeiro ao último, até encontrar ou até eles acabarem. Ela também é chamada de busca sequencial.

No artigo sobre a recursividade, avisei que estávamos a caminho dos algoritmos de busca e ordenação. Chegou a hora! E começaremos pela mais simples das buscas.

Pense em um molho de chaves que você nunca usou. Para abrir a porta, você testa a primeira chave. Não abriu? Testa a segunda. E segue assim, uma por uma, até a porta abrir ou as chaves acabarem. Você não pula nenhuma, porque nada no molho diz onde a chave certa está. Isso é busca linear!!!

História em quadrinhos em três quadros: uma pessoa com um molho de seis chaves diante de uma porta testa uma chave de cada vez; as três primeiras não abrem e a quarta abre a porta
A busca linear no molho de chaves: uma por uma, na ordem, até a porta abrir.

Como funciona a busca linear?

O algoritmo repete sempre os mesmos passos:

  • Olha o elemento da posição atual, começando pela primeira.
  • Se for o valor procurado, achou. Devolve a posição e para.
  • Se não for, vai para a posição seguinte e repete.
  • Se as posições acabarem, o valor não está lá.

Repare em um detalhe que faz toda a diferença: em nenhum passo o algoritmo precisa que os dados estejam em ordem. A busca linear funciona com o vetor do jeito que ele estiver. É o algoritmo de busca mais simples que existe.

Exemplo de busca linear passo a passo

Vamos procurar o número 67 neste vetor de 10 posições. Ele está fora de ordem, de propósito:

Posição0123456789
Valor523801225767183140
Vetor fora de ordem usado no exemplo.
PassoPosiçãoValorÉ o 67?
1052não: segue para a próxima
213não: segue para a próxima
3280não: segue para a próxima
4312não: segue para a próxima
5425não: segue para a próxima
657não: segue para a próxima
7667sim: achou na posição 6
Passo a passo da busca linear pelo número 67.
Vetor de dez posições fora de ordem com a busca linear pelo 67: seis comparações com resposta não e a sétima, na posição 6, com achou
A busca pelo 67: sete comparações, uma para cada posição olhada.

Foram sete comparações, e as posições 7, 8 e 9 nem precisaram ser olhadas. Assim que o valor aparece, a busca para.

Ver a animação da busca linear, passo a passo
Animação da busca linear pelo 67 em um vetor de dez posições, comparando um elemento por vez até achar na posição 6
O mesmo exemplo em movimento: a seta anda uma posição por vez, e as posições já olhadas ficam marcadas.

Busca linear em Python, PHP, C e JavaScript

O programa abaixo faz o mesmo nas quatro linguagens: procura quatro valores no vetor do exemplo e mostra a posição de cada um. Quando o valor não está no vetor, a função devolve -1.

Python:

# Busca linear: procurar um valor olhando os elementos um por um

def busca_linear(numeros, alvo):
    for posicao in range(len(numeros)):
        if numeros[posicao] == alvo:
            return posicao              # achou: devolve a posição e para
    return -1                           # olhou todos e não achou

numeros = [52, 3, 80, 12, 25, 7, 67, 18, 31, 40]

print("posição do 67:", busca_linear(numeros, 67))
print("posição do 52:", busca_linear(numeros, 52))
print("posição do 40:", busca_linear(numeros, 40))
print("posição do 5:", busca_linear(numeros, 5))

PHP:

<?php
// Busca linear: procurar um valor olhando os elementos um por um

function buscaLinear(array $numeros, int $alvo): int
{
    for ($posicao = 0; $posicao < count($numeros); $posicao++) {
        if ($numeros[$posicao] === $alvo) {
            return $posicao;            // achou: devolve a posição e para
        }
    }
    return -1;                          // olhou todos e não achou
}

$numeros = [52, 3, 80, 12, 25, 7, 67, 18, 31, 40];

echo "posição do 67: ", buscaLinear($numeros, 67), "\n";
echo "posição do 52: ", buscaLinear($numeros, 52), "\n";
echo "posição do 40: ", buscaLinear($numeros, 40), "\n";
echo "posição do 5: ", buscaLinear($numeros, 5), "\n";

C:

/* Busca linear: procurar um valor olhando os elementos um por um */
#include <stdio.h>

int busca_linear(int numeros[], int tamanho, int alvo) {
    for (int posicao = 0; posicao < tamanho; posicao++) {
        if (numeros[posicao] == alvo) {
            return posicao;             /* achou: devolve a posição e para */
        }
    }
    return -1;                          /* olhou todos e não achou */
}

int main(void) {
    int numeros[] = {52, 3, 80, 12, 25, 7, 67, 18, 31, 40};
    int tamanho = 10;

    printf("posição do 67: %d\n", busca_linear(numeros, tamanho, 67));
    printf("posição do 52: %d\n", busca_linear(numeros, tamanho, 52));
    printf("posição do 40: %d\n", busca_linear(numeros, tamanho, 40));
    printf("posição do 5: %d\n", busca_linear(numeros, tamanho, 5));
    return 0;
}

JavaScript:

// Busca linear: procurar um valor olhando os elementos um por um

function buscaLinear(numeros, alvo) {
  for (let posicao = 0; posicao < numeros.length; posicao++) {
    if (numeros[posicao] === alvo) {
      return posicao; // achou: devolve a posição e para
    }
  }
  return -1; // olhou todos e não achou
}

const numeros = [52, 3, 80, 12, 25, 7, 67, 18, 31, 40];

console.log("posição do 67:", buscaLinear(numeros, 67));
console.log("posição do 52:", buscaLinear(numeros, 52));
console.log("posição do 40:", buscaLinear(numeros, 40));
console.log("posição do 5:", buscaLinear(numeros, 5));

Saída:

posição do 67: 6
posição do 52: 0
posição do 40: 9
posição do 5: -1

A saída é a mesma. Um laço for percorre as posições, e um if compara cada elemento com o valor procurado. O return dentro do laço é o que faz a busca parar na hora em que acha. Já o -1 do fim só é alcançado quando o laço olhou todos os elementos e não achou nada. Por que -1? Porque nenhuma posição de vetor é negativa, então não há como confundir com uma resposta de verdade.

Foque no conceito, e não na linguagem! Nas quatro, a ideia é a mesma: olhar um por um e parar quando achar.

Quantas comparações a busca linear faz?

Depende de onde o valor está. Por isso se fala em três casos:

  • Melhor caso: o valor está na primeira posição. Uma comparação e pronto.
  • Pior caso: o valor está na última posição ou não está no vetor. A busca olha todos os elementos.
  • Caso médio: se o valor pode estar em qualquer posição, com a mesma chance, a busca olha em média pouco mais da metade do vetor.

Este programa conta as comparações no vetor do exemplo:

# Quantas comparações a busca linear faz?

def comparacoes(numeros, alvo):
    feitas = 0
    for valor in numeros:
        feitas = feitas + 1             # uma comparação para cada elemento olhado
        if valor == alvo:
            break
    return feitas

numeros = [52, 3, 80, 12, 25, 7, 67, 18, 31, 40]

print("52, o primeiro:", comparacoes(numeros, 52))
print("67, no meio do caminho:", comparacoes(numeros, 67))
print("40, o último:", comparacoes(numeros, 40))
print("5, que não está no vetor:", comparacoes(numeros, 5))

total = 0
for valor in numeros:
    total = total + comparacoes(numeros, valor)
print("média, buscando cada um dos 10 valores:", total / len(numeros))

Saída:

52, o primeiro: 1
67, no meio do caminho: 7
40, o último: 10
5, que não está no vetor: 10
média, buscando cada um dos 10 valores: 5.5
Barras com o número de comparações da busca linear em um vetor de dez valores: 1 no melhor caso, 5,5 no caso médio e 10 no pior caso
Os três casos no vetor de 10 valores: 1 comparação no melhor, 5,5 na média e 10 no pior.

Aí você pergunta: o que é esse n?

Calma! O n é uma letra que fica no lugar de um número. Aqui, esse número é a quantidade de valores do vetor, que a análise de algoritmos chama de tamanho da entrada. No vetor do exemplo, n = 10. Em uma lista com 500 nomes, n = 500.

E por que não escrever logo o número? Porque a conta precisa valer para qualquer vetor, e não só para o do exemplo. Sem a letra, seria preciso dizer: no vetor de 10 valores o pior caso faz 10 comparações, no de 500 faz 500, no de 1.000 faz 1.000… e a lista nunca acabaria. Com a letra, uma frase resolve: no vetor de n valores, o pior caso faz n comparações.

Essa ideia vem da álgebra, a mesma do x das equações da escola. Em 1591, o matemático francês François Viète publicou um livro em que as letras representavam números, tanto os desconhecidos quanto os conhecidos: vogais para uns, consoantes para os outros. Em 1637, René Descartes adotou as primeiras letras do alfabeto (a, b, c) para os valores conhecidos e as últimas (x, y, z) para os desconhecidos. É a convenção usada até hoje.

O n é mais uma dessas letras. A diferença está no que ele representa: o x costuma ser um valor a descobrir, e o n é uma quantidade que você conhece na hora de rodar o programa, mas que muda de um vetor para outro. A letra poderia ser outra. O n é o costume: é ele que aparece nas aulas de análise de algoritmos listadas nas fontes deste artigo.

Um detalhe: como o n conta elementos, ele é sempre um número inteiro. Existe vetor com 3 valores e vetor com 4, mas não com 3,5.

Sacou? Onde estiver escrito n, leia “a quantidade de valores do vetor”. Com isso, as contas da busca linear cabem em uma linha:

Para um vetor com n elementos, o melhor caso faz 1 comparação, o pior faz n e o caso médio faz (n + 1) ÷ 2. No vetor de 10 valores, a média é (10 + 1) ÷ 2 = 5,5, exatamente o que o programa mostrou.

Tamanho do vetor (n)Melhor casoCaso médioPior caso
1015,510
1.0001500,51.000
1.000.0001500.000,51.000.000
Comparações da busca linear conforme o vetor cresce.

Quais medidas são usadas para explicar o Big O?

O número de comparações cresce junto com o tamanho do vetor: dobrou o vetor, dobrou o trabalho no pior caso. Por isso se diz que a busca linear tem complexidade O(n). Para chegar até aqui, você já usou as medidas com que a análise de algoritmos trabalha. Veja o resumo:

MedidaO que éNa busca linear
Tamanho da entrada (n)A quantidade de dados que o algoritmo recebeOs n valores do vetor
Operação contadaA operação relevante, que se repeteA comparação de um valor com o alvo
Melhor casoA entrada que dá menos trabalho1 comparação
Caso médioA média do trabalho, com todas as posições igualmente prováveis(n + 1) ÷ 2 comparações
Pior casoA entrada que dá mais trabalhon comparações
Ordem de crescimentoComo a contagem cresce quando o n cresceLinear: O(n)
As medidas da análise de algoritmos aplicadas à busca linear.

Repare no que ficou de fora: o tempo em segundos. Ele depende do computador e do compilador, e a ideia é comparar algoritmos sem depender da máquina. Por isso se conta quantas vezes a operação relevante é executada, e essa contagem é escrita em função de n.

A notação Big O guarda só a ordem de crescimento: ela dá um limite superior para a contagem e ignora as constantes que somam ou multiplicam. O caso médio, (n + 1) ÷ 2, é metade de n mais meio. Tirando as constantes, sobra o n. Então o caso médio e o pior caso da busca linear são, os dois, O(n). Já o melhor caso faz 1 comparação com qualquer n: é O(1), o custo que não depende do tamanho da entrada.

ATENÇÃO: quando alguém diz apenas “esse algoritmo é O(n)”, em geral está falando do pior caso, que é a medida principal da análise.

Vou repetir porque é importante: o Big O não diz quantos segundos o programa leva. Ele diz como o trabalho cresce quando o n cresce. Se essa notação ainda é novidade para você, veja como calcular a complexidade de algoritmos.

Aí você pergunta: existe uma busca mais rápida do que a linear?

Existe! É a busca binária, o assunto do próximo artigo. Ela faz no máximo 20 comparações em um vetor de um milhão de valores, contra um milhão da busca linear no pior caso. Só que ela cobra um preço: o vetor precisa estar ordenado.

No próximo artigo, faço um teste com este mesmo vetor fora de ordem: a busca binária procura o 52 e responde -1, como se ele não estivesse lá. A busca linear, você viu na saída do programa, achou o 52 na posição 0, logo na primeira comparação.

Por isso a busca linear é a escolha certa em três situações:

  • O vetor não está ordenado. A busca binária não funciona, a linear funciona.
  • O vetor é pequeno. Com poucos valores, a diferença entre as duas quase não aparece.
  • A busca é uma só. Ordenar o vetor também tem um custo, maior que o de uma busca linear. Não vale a pena ordenar tudo para procurar uma única vez.

Vou repetir porque é importante: a busca binária exige o vetor ordenado, a busca linear não exige nada. Sacou?

Preciso escrever a busca linear toda vez?

No dia a dia, não. As linguagens já trazem funções prontas para procurar um valor em uma lista, cada uma com os seus nomes:

LinguagemPara saber se o valor existePara saber a posiçãoQuando não acha
Pythonvalor in listalista.index(valor)erro ValueError
PHPin_arrayarray_searchfalse
JavaScriptincludesindexOf-1
As funções prontas de três linguagens, testadas com o vetor do exemplo.

Testei as três com o vetor do exemplo. Para o 67, todas responderam que ele existe e que está na posição 6. Para o 5, que não está no vetor, cada uma respondeu do seu jeito: o index do Python parou o programa com um erro, o array_search do PHP devolveu false e o indexOf do JavaScript devolveu -1. O erro do Python foi este:

ValueError: 5 is not in list

ATENÇÃO: no PHP, o array_search devolve a posição, e a posição pode ser 0. Procurei o 52, que está na posição 0, e testei o resultado com um if simples. O PHP tratou o 0 como falso e respondeu “não achou”, com o 52 logo na frente! O manual do PHP avisa sobre isso e manda testar o retorno com o operador ===. Com if ($posicao !== false), a resposta foi a certa: achou na posição 0.

Outro cuidado: o in_array do PHP faz a comparação frouxa, a menos que você peça a estrita. No meu teste, in_array(“67”, $numeros) respondeu verdadeiro, mesmo com o 67 guardado como número e procurado como texto. Com o terceiro argumento true, a resposta virou falso. No JavaScript foi o contrário: o indexOf(“67”) devolveu -1, porque ele usa a igualdade estrita, a do ===.

Em C, o caminho é o laço escrito à mão, como no programa deste artigo.

Mesmo com as funções prontas, escreva a busca linear na mão pelo menos uma vez. Quem entende como a ferramenta funciona por dentro sabe quando usar e sabe o que fazer quando ela não serve.

Quais são os erros mais comuns na busca linear?

  • Continuar procurando depois de achar. Sem o return (ou o break) dentro do laço, o programa olha o vetor inteiro à toa.
  • Esquecer o caso em que o valor não existe. Toda busca precisa de uma resposta para “não achei”. Aqui, é o -1.
  • Confundir a posição 0 com “não achei”. O 0 é uma posição válida. É a pegadinha do array_search no PHP.
  • Errar a última posição. Em um vetor de 10 valores, a última posição é a 9, e não a 10.
  • Comparar tipos diferentes sem perceber. O texto “67” e o número 67 são iguais para o in_array do PHP e diferentes para o indexOf do JavaScript.
  • Usar a busca linear em um vetor enorme e já ordenado. Se a ordem já existe, a busca binária faz o mesmo serviço com muito menos comparações.

Agora é com você!

No papel:

  • No vetor do exemplo, quantas comparações a busca linear faz para achar o 25? E para descobrir que o 99 não está lá?
  • Um vetor tem 200 valores. Quantas comparações a busca linear faz no melhor caso, no pior caso e, em média, quando o valor está no vetor?
  • O valor procurado aparece duas vezes no vetor. Qual das duas posições a função deste artigo devolve? Por quê?

No computador:

  • Mude a função para contar quantas vezes o valor aparece no vetor, em vez de parar no primeiro.
  • Escreva uma função que devolve a posição da última ocorrência do valor. Dica: dá para percorrer o vetor do fim para o começo.
  • Escreva uma busca linear que procura um nome em uma lista de nomes.

Tente sozinho, sem pedir a resposta pronta para ninguém, nem para a IA!

A busca linear não exige nada do vetor, mas olha os valores um por um. E se o vetor já estiver ordenado? Aí dá para descartar metade dele a cada comparação! No próximo artigo você conhecerá a busca binária. Até lá!

Confiança Sempre!!!

Fontes:

Sobre quem escreve

Walmir Silva

Olá! Sou Walmir, engenheiro de software com MBA em Engenharia de Software e o cérebro por trás do GrowthCode e autor do livro "Além do Código".

Se você acha que programação é apenas sobre escrever código, prepare-se para expandir seus horizontes. Aqui, nós vamos além do código e exploramos as interseções fascinantes entre tecnologia, negócios, artes e filosofia.

Você está em busca de crescimento na carreira? Quer se destacar em um mercado competitivo? Almeja uma vida mais rica em conhecimento e realização? Então você chegou ao lugar certo. No GrowthCode, oferecemos insights profundos, estratégias comprovadas e um toque de sabedoria filosófica para catalisar seu crescimento pessoal e profissional.

Ver todos os artigos →

Continue a conversa

Compartilhe sua perspectiva

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Encontre sua próxima resposta

O que você quer aprender?

Preferências de cookies

Os cookies opcionais começam desligados. Você pode mudar a escolha a qualquer momento por esta tela.

NecessáriosSempre ativos

Guardam a sua escolha de cookies e mantêm o site funcionando. Não são usados para publicidade.

Contam visitas e mostram como o site é usado: Google Analytics e Microsoft Clarity, carregados pelo Google Tag Manager. Como esse contêiner também carrega tags de publicidade, as estatísticas só são ativadas junto com Publicidade e marketing.

Exibem anúncios do Google AdSense e medem campanhas e e-mails: pixels da Meta e do TikTok e o Mautic.

Permite que o Google escolha anúncios com base nos seus interesses. Desligado, os anúncios aparecem sem personalização. Depende de Publicidade e marketing.

Também é possível bloquear cookies nas configurações do navegador. Detalhes na Política de privacidade.