Neste artigo
- Como funciona a busca linear?
- Exemplo de busca linear passo a passo
- Busca linear em Python, PHP, C e JavaScript
- Quantas comparações a busca linear faz?
- Aí você pergunta: o que é esse n?
- Quais medidas são usadas para explicar o Big O?
- Aí você pergunta: existe uma busca mais rápida do que a linear?
- Preciso escrever a busca linear toda vez?
- Quais são os erros mais comuns na busca linear?
- 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!!!

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ção | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Valor | 52 | 3 | 80 | 12 | 25 | 7 | 67 | 18 | 31 | 40 |
| Passo | Posição | Valor | É o 67? |
|---|---|---|---|
| 1 | 0 | 52 | não: segue para a próxima |
| 2 | 1 | 3 | não: segue para a próxima |
| 3 | 2 | 80 | não: segue para a próxima |
| 4 | 3 | 12 | não: segue para a próxima |
| 5 | 4 | 25 | não: segue para a próxima |
| 6 | 5 | 7 | não: segue para a próxima |
| 7 | 6 | 67 | sim: achou na posição 6 |

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

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

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 caso | Caso médio | Pior caso |
|---|---|---|---|
| 10 | 1 | 5,5 | 10 |
| 1.000 | 1 | 500,5 | 1.000 |
| 1.000.000 | 1 | 500.000,5 | 1.000.000 |
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:
| Medida | O que é | Na busca linear |
|---|---|---|
| Tamanho da entrada (n) | A quantidade de dados que o algoritmo recebe | Os n valores do vetor |
| Operação contada | A operação relevante, que se repete | A comparação de um valor com o alvo |
| Melhor caso | A entrada que dá menos trabalho | 1 comparação |
| Caso médio | A média do trabalho, com todas as posições igualmente prováveis | (n + 1) ÷ 2 comparações |
| Pior caso | A entrada que dá mais trabalho | n comparações |
| Ordem de crescimento | Como a contagem cresce quando o n cresce | Linear: O(n) |
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:
| Linguagem | Para saber se o valor existe | Para saber a posição | Quando não acha |
|---|---|---|---|
| Python | valor in lista | lista.index(valor) | erro ValueError |
| PHP | in_array | array_search | false |
| JavaScript | includes | indexOf | -1 |
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:
- Unicamp, Instituto de Computação, MC-102, aula 11, Busca em Vetores, com a busca sequencial como o algoritmo mais simples de busca, o melhor caso na posição 0, o pior caso quando a chave é a última ou não pertence ao vetor e a exigência de vetor ordenado na busca binária (PDF, slides de aula).
- Unicamp, Instituto de Computação, MC-102, aula 15, busca e ordenação, com as comparações da busca sequencial no melhor caso, no pior caso e no caso médio e o aviso de que não vale a pena ordenar o vetor para fazer uma só busca (PDF, slides de aula).
- Unicamp, Instituto de Computação, MC-102, Busca binária e sequencial, com o código da busca sequencial, as 1.000 comparações no pior caso para n = 1000 contra 10 da busca binária e o custo de ordenar o vetor (PDF, slides de aula).
- UFSCar, Departamento de Computação, Algoritmos e Estruturas de Dados 1, aula 6, com a busca sequencial que devolve -1 quando não encontra, o pior caso em que o vetor inteiro é percorrido, da ordem de n operações, e a variação que percorre do fim para o início (PDF).
- UTFPR, Departamento Acadêmico de Informática, aula 12, Algoritmos de Pesquisa, com a análise da pesquisa sequencial: melhor caso 1, pior caso n e caso médio (n + 1) / 2 (PDF, slides de aula).
- University of Illinois, CS 173, lecture 23, Algorithms, com o pior caso da busca linear, quando o valor está no fim ou não está no vetor, e a conta do caso médio, (n + 1) / 2 (PDF, em inglês).
- Virginia Tech, OpenDSA, Analyzing Search in Unsorted Lists, com o custo de i + 1 comparações quando o valor está na posição i e de n comparações quando ele não está na lista (em inglês).
- University of Waterloo, Chapter 12: Searching and Sorting Algorithms, com o melhor caso, o pior caso e o caso médio da busca linear (PDF, em inglês).
- Universidade Federal do Vale do São Francisco, aula 21, complexidade de algoritmos, com o tamanho da entrada como o número de valores de um vetor, a função T(n) que conta as execuções de uma operação relevante, a medição em segundos que depende do compilador e do computador, os três casos da busca sequencial, o pior caso como medida principal e a notação O como limite superior que ignora constantes (PDF).
- PUC-Rio, Departamento de Informática, Complexidade de algoritmos, com o tamanho do problema como o parâmetro n, o descarte dos termos inferiores e das constantes multiplicativas e a classe O(1), que independe do tamanho n da entrada (PDF, slides de aula).
- University of St Andrews, MacTutor, Earliest Uses of Symbols for Variables, com François Viète como o primeiro a usar letras para incógnitas e constantes em equações, em 1591, com vogais e consoantes, e a convenção de René Descartes em La Géométrie, de 1637 (em inglês).
- Infopédia, Porto Editora, artigo Álgebra, com o uso de letras para representar as incógnitas no início da Era Moderna e as notações a, b, c e x, y, z estabelecidas por Descartes.
- Manual do PHP, in_array, com a função que verifica se um valor existe em um array, a comparação frouxa por padrão e o parâmetro strict (em inglês).
- Manual do PHP, array_search, com a função que devolve a chave do primeiro elemento encontrado ou false e o aviso para testar o retorno com o operador === (em inglês).
- MDN Web Docs, Array.prototype.indexOf(), com o índice da primeira ocorrência ou -1 e a comparação por igualdade estrita (em inglês).
- Os exemplos foram executados em Python 3.13, PHP 8.3, GCC 13 e Node.js 22.

Continue a conversa