Busca linear
Última atualização
A busca linear (também chamada de busca sequencial) é o algoritmo de busca mais simples: comece no primeiro elemento e compare cada um com o alvo até encontrar uma correspondência ou os elementos acabarem. Ela não faz nenhuma suposição sobre os dados — o array pode estar desordenado, e os elementos podem ser qualquer coisa que possa ser comparada por igualdade.
A animação acima destaca cada comparação enquanto a varredura avança da esquerda para a direita e para no momento em que o alvo aparece. Sua simplicidade custa velocidade: no pior caso todos os elementos são verificados, então ela roda em O(n). Quando os dados estão ordenados, a busca binária encontra a mesma resposta em O(log n) — e se você precisar de dados ordenados primeiro, veja o merge sort.
Complexidade de tempo e espaço
| Caso | Complexidade | Observações |
|---|---|---|
| Melhor caso | O(1) | O primeiro elemento é o alvo. |
| Caso médio | O(n) | Em média, metade dos elementos é verificada antes de um acerto. |
| Pior caso | O(n) | O alvo é o último — ou não está presente. |
| Espaço | O(1) | Apenas o índice atual é mantido. |
Passo a passo
| Passo | O que acontece |
|---|---|
| 1 | Comece no índice 0, o primeiro elemento do array. |
| 2 | Compare o elemento atual com o valor-alvo. |
| 3 | Se forem iguais, retorne o índice atual — encontrado. |
| 4 | Caso contrário, avance uma posição para a direita e repita. |
| 5 | Se o fim do array for alcançado sem correspondência, o alvo não está presente (retorne -1). |
Exemplo resolvido
Buscando 5 em [7, 3, 9, 1, 5, 8, 2]:
| Comparação | Índice | Elemento | Resultado |
|---|---|---|---|
| 1 | 0 | 7 | 7 ≠ 5 — continue varrendo. |
| 2 | 1 | 3 | 3 ≠ 5 — continue varrendo. |
| 3 | 2 | 9 | 9 ≠ 5 — continue varrendo. |
| 4 | 3 | 1 | 1 ≠ 5 — continue varrendo. |
| 5 | 4 | 5 | 5 = 5 — encontrado no índice 4. |
Quando usar a busca linear
| Use quando | Evite quando |
|---|---|
| Os dados estão desordenados ou mudam constantemente | Os dados estão ordenados — a busca binária é exponencialmente mais rápida |
| A coleção é pequena, então a simplicidade vence | O conjunto de dados é grande e buscado repetidamente |
| Você só tem acesso sequencial (streams, listas encadeadas) | Você pode manter um índice ou uma tabela hash para buscas em O(1) |
Código de Linear Search
Uma implementação limpa e executável de Linear Search em Python, JavaScript, Java, C++, C, Pseudocode. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Linear Search em Python
Python
1def linear_search(a, target):2 # Scan left to right until the target appears3 for i in range(len(a)):4 if a[i] == target:5 return i6 return -17
8
9nums = [7, 3, 9, 1, 5, 8, 2]10print("Index of 5:", linear_search(nums, 5))11print("Index of 4:", linear_search(nums, 4))Código de Linear Search em JavaScript
JavaScript
1function linearSearch(a, target) {2 // Scan left to right until the target appears3 for (let i = 0; i < a.length; i++) {4 if (a[i] === target) return i;5 }6 return -1;7}8
9const nums = [7, 3, 9, 1, 5, 8, 2];10console.log("Index of 5:", linearSearch(nums, 5));11console.log("Index of 4:", linearSearch(nums, 4));Código de Linear Search em Java
Java
1public class Main {2 static int linearSearch(int[] a, int target) {3 // Scan left to right until the target appears4 for (int i = 0; i < a.length; i++) {5 if (a[i] == target) return i;6 }7 return -1;8 }9
10 public static void main(String[] args) {11 int[] nums = {7, 3, 9, 1, 5, 8, 2};12 System.out.println("Index of 5: " + linearSearch(nums, 5));13 System.out.println("Index of 4: " + linearSearch(nums, 4));14 }15}Código de Linear Search em C++
C++
1#include <iostream>2#include <vector>3
4int linearSearch(const std::vector<int>& a, int target) {5 // Scan left to right until the target appears6 for (std::size_t i = 0; i < a.size(); i++) {7 if (a[i] == target) return static_cast<int>(i);8 }9 return -1;10}11
12int main() {13 std::vector<int> nums = {7, 3, 9, 1, 5, 8, 2};14 std::cout << "Index of 5: " << linearSearch(nums, 5) << "\n";15 std::cout << "Index of 4: " << linearSearch(nums, 4) << "\n";16 return 0;17}Código de Linear Search em C
C
1#include <stdio.h>2
3int linear_search(const int a[], int n, int target) {4 /* Scan left to right until the target appears */5 for (int i = 0; i < n; i++) {6 if (a[i] == target) return i;7 }8 return -1;9}10
11int main(void) {12 int nums[] = {7, 3, 9, 1, 5, 8, 2};13 int n = sizeof(nums) / sizeof(nums[0]);14 printf("Index of 5: %d\n", linear_search(nums, n, 5));15 printf("Index of 4: %d\n", linear_search(nums, n, 4));16 return 0;17}Código de Linear Search em Pseudocode
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211
12FUNCTION linearSearch(target : INTEGER) RETURNS INTEGER13 DECLARE i : INTEGER14 // Scan left to right until the target appears15 FOR i ← 1 TO n16 IF nums[i] = target THEN17 RETURN i18 ENDIF19 NEXT i20 RETURN -121ENDFUNCTION22
23OUTPUT "Index of 5 is ", linearSearch(5)24OUTPUT "Index of 4 is ", linearSearch(4)Perguntas frequentes sobre busca linear
Qual é a complexidade de tempo da busca linear?
O(n) nos casos médio e pior — a varredura pode ter que visitar todos os elementos — e O(1) no melhor caso, quando o primeiro elemento é o alvo. Ela usa O(1) de espaço extra.A busca linear precisa de dados ordenados?
Não — essa é sua principal vantagem. A busca linear funciona em dados completamente desordenados porque verifica a igualdade de cada elemento; a ordem nunca importa. A busca binária, por outro lado, só funciona em arrays ordenados.
Quando a busca linear é melhor que a busca binária?
Quando os dados estão desordenados e são buscados apenas uma vez (ordenar primeiro custaria
O(n log n)), quando a coleção é minúscula, ou quando você só tem acesso sequencial, como um stream ou uma lista encadeada. Para buscas repetidas em arrays ordenados, a busca binária vence.Busca linear é o mesmo que busca sequencial?
Sim — os dois nomes descrevem o mesmo algoritmo: percorrer os elementos em sequência até encontrar o alvo ou a coleção terminar.
Quantas comparações a busca linear faz em média?
Se o alvo está presente e tem a mesma probabilidade de estar em qualquer posição, cerca de
n/2 comparações em média; se o alvo está ausente, exatamente n. Esse crescimento linear é o motivo do nome busca linear.Recursos relacionados
Mais visualizações
