Nem toda busca pode (ou deve) usar a estratégia binária. A Busca Linear (sequential search) é o algoritmo de busca mais simples e fundamental: percorre os elementos um a um até encontrar o alvo ou esgotar a lista. A Busca Sentinela é uma otimização da busca linear que elimina uma comparação por iteração. A Busca por Interpolação (interpolation search) é uma variante inteligente que estima a posição do alvo com base no seu valor, alcançando O(log log n) para dados uniformemente distribuídos.
Esses algoritmos complementam a Busca Binária: a busca linear funciona em dados não ordenados, a busca sentinela é útil quando o overhead de cada iteração importa, e a busca por interpolação supera a binária quando a distribuição dos dados é conhecida e uniforme. Juntos, eles cobrem todo o espectro de problemas de busca.
Como Funciona
Busca Linear
A busca linear examina cada elemento sequencialmente, do primeiro ao último:
Buscar o valor 7 no vetor [3, 8, 1, 7, 5, 2]:
Passo 1: vetor[0] = 3 ≠ 7 → próximo
[3, 8, 1, 7, 5, 2]
^
Passo 2: vetor[1] = 8 ≠ 7 → próximo
[3, 8, 1, 7, 5, 2]
^
Passo 3: vetor[2] = 1 ≠ 7 → próximo
[3, 8, 1, 7, 5, 2]
^
Passo 4: vetor[3] = 7 == 7 → ENCONTRADO no índice 3!
[3, 8, 1, 7, 5, 2]
^
Total: 4 comparações
Busca Sentinela
A busca sentinela coloca o valor buscado no final do vetor, eliminando a verificação de limites no loop:
Buscar 7 em [3, 8, 1, 5, 2]:
Passo 0: colocar sentinela (7) no final
[3, 8, 1, 5, 2, 7] ← sentinela
^
Loop (sem verificar limites — a sentinela garante que vamos parar):
vetor[0]=3 ≠ 7, vetor[1]=8 ≠ 7, vetor[2]=1 ≠ 7,
vetor[3]=5 ≠ 7, vetor[4]=2 ≠ 7, vetor[5]=7 == 7 → parou!
Posição 5 == posição da sentinela → NÃO ENCONTRADO
(Se tivesse parado antes da sentinela → encontrado)
Busca por Interpolação
Em vez de sempre ir ao meio (como a busca binária), a interpolação estima a posição com base no valor:
Buscar 67 no vetor uniformemente distribuído:
Índice: [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
Valor: 10 20 30 40 50 60 70 80 90 100
Fórmula: pos = esq + ((alvo - vetor[esq]) * (dir - esq)) / (vetor[dir] - vetor[esq])
=== Iteração 1 ===
esq=0, dir=9
pos = 0 + ((67 - 10) * (9 - 0)) / (100 - 10)
pos = 0 + (57 * 9) / 90
pos = 0 + 5 = 5 (arredondado)
vetor[5] = 60 < 67 → buscar à direita (esq = 6)
=== Iteração 2 ===
esq=6, dir=9
pos = 6 + ((67 - 70) * (9 - 6)) / (100 - 70)
pos = 6 + (-3 * 3) / 30
pos = 6 + (-0.3) = 6 (arredondado)
vetor[6] = 70 > 67 → buscar à esquerda (dir = 5)
esq > dir → NÃO ENCONTRADO
Total: 2 iterações (busca binária faria 3-4)
Diagrama comparativo — como cada algoritmo escolhe onde buscar:
Vetor: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
Alvo: 80
Busca Linear: → → → → → → → ✓ (7 passos)
10 20 30 40 50 60 70 80
Busca Binária: meio=50 → direita → meio=80 ✓ (2 passos)
↓
[60, 70, 80, 90, 100]
↓
80 ✓
Interpolação: pos ≈ 0 + (80-10)/(100-10) * 9 ≈ 7 → 80 ✓ (1 passo!)
Salta direto para a posição estimada
Complexidade
Busca Linear
| Caso | Tempo | Espaço |
|---|---|---|
| Melhor | O(1) | O(1) |
| Médio | O(n) | O(1) |
| Pior | O(n) | O(1) |
- Melhor caso O(1): o elemento buscado é o primeiro do vetor.
- Médio e pior caso O(n): em média, percorre metade do vetor. No pior caso, percorre todos os elementos.
- Não requer ordenação: funciona em qualquer vetor.
Busca Sentinela
| Caso | Tempo | Espaço |
|---|---|---|
| Melhor | O(1) | O(1) |
| Médio | O(n) | O(1) |
| Pior | O(n) | O(1) |
- Mesma complexidade assintótica da busca linear, mas com constante menor por eliminar uma comparação de limites por iteração (apenas 1 comparação por passo em vez de 2).
Busca por Interpolação
| Caso | Tempo | Espaço |
|---|---|---|
| Melhor | O(1) | O(1) |
| Médio | O(log log n)* | O(1) |
| Pior | O(n) | O(1) |
- Médio O(log log n): para dados uniformemente distribuídos, a estimativa da posição é tão boa que o espaço de busca diminui exponencialmente mais rápido que na busca binária.
- Pior caso O(n): quando os dados são muito desiguais (ex: exponencialmente distribuídos), a estimativa pode ser ruim, degenerando para busca linear.
- Pré-requisito: vetor ordenado (como busca binária) + distribuição razoavelmente uniforme.
Implementação em Rust
Busca Linear
/// Busca linear genérica.
/// Retorna Some(índice) do primeiro elemento igual ao alvo, ou None.
/// Funciona em vetores não ordenados.
fn busca_linear<T: PartialEq>(vetor: &[T], alvo: &T) -> Option<usize> {
for (i, elemento) in vetor.iter().enumerate() {
if elemento == alvo {
return Some(i);
}
}
None
}
/// Busca linear que retorna TODOS os índices onde o alvo aparece.
fn buscar_todos<T: PartialEq>(vetor: &[T], alvo: &T) -> Vec<usize> {
vetor
.iter()
.enumerate()
.filter(|(_, elem)| *elem == alvo)
.map(|(i, _)| i)
.collect()
}
/// Busca linear com predicado — encontrar o primeiro que satisfaz uma condição.
fn buscar_por<T, F>(vetor: &[T], predicado: F) -> Option<usize>
where
F: Fn(&T) -> bool,
{
vetor.iter().position(|elem| predicado(elem))
}
fn main() {
let numeros = vec![3, 8, 1, 7, 5, 2, 7, 9];
println!("Buscar 7: {:?}", busca_linear(&numeros, &7)); // Some(3)
println!("Buscar 4: {:?}", busca_linear(&numeros, &4)); // None
println!("Todos os 7: {:?}", buscar_todos(&numeros, &7)); // [3, 6]
println!("Primeiro par: {:?}", buscar_por(&numeros, |x| x % 2 == 0)); // Some(1)
// Funciona com strings não ordenadas
let frutas = vec!["manga", "abacaxi", "uva", "pêra", "uva"];
println!("\nBuscar 'uva': {:?}", busca_linear(&frutas, &"uva")); // Some(2)
println!("Todas 'uva': {:?}", buscar_todos(&frutas, &"uva")); // [2, 4]
}
Busca Sentinela
/// Busca sentinela — elimina verificação de limites no loop.
/// Nota: requer vetor mutável temporariamente.
fn busca_sentinela(vetor: &mut Vec<i32>, alvo: i32) -> Option<usize> {
let n = vetor.len();
if n == 0 {
return None;
}
// Salvar o último elemento e colocar a sentinela
let ultimo = vetor[n - 1];
// Se o último elemento é o alvo, retornar imediatamente
if ultimo == alvo {
return Some(n - 1);
}
vetor[n - 1] = alvo; // colocar sentinela
let mut i = 0;
// Loop sem verificação de limites — a sentinela garante a parada
while vetor[i] != alvo {
i += 1;
}
// Restaurar o último elemento
vetor[n - 1] = ultimo;
// Verificar se encontrou antes da sentinela
if i < n - 1 {
Some(i)
} else {
None
}
}
fn main() {
let mut v = vec![3, 8, 1, 7, 5, 2, 9, 4];
println!("Buscar 7: {:?}", busca_sentinela(&mut v, 7)); // Some(3)
println!("Buscar 6: {:?}", busca_sentinela(&mut v, 6)); // None
println!("Vetor intacto: {:?}", v); // [3, 8, 1, 7, 5, 2, 9, 4]
}
Busca por Interpolação
/// Busca por interpolação.
/// Funciona melhor em vetores ordenados com distribuição uniforme.
/// Retorna Some(índice) se encontrado, None caso contrário.
fn busca_interpolacao(vetor: &[i64], alvo: i64) -> Option<usize> {
if vetor.is_empty() {
return None;
}
let mut esquerda: usize = 0;
let mut direita: usize = vetor.len() - 1;
while esquerda <= direita
&& alvo >= vetor[esquerda]
&& alvo <= vetor[direita]
{
// Se esquerda == direita, verificar diretamente
if esquerda == direita {
if vetor[esquerda] == alvo {
return Some(esquerda);
}
return None;
}
// Estimar a posição usando interpolação linear
let denominador = vetor[direita] - vetor[esquerda];
if denominador == 0 {
// Todos os elementos entre esquerda e direita são iguais
if vetor[esquerda] == alvo {
return Some(esquerda);
}
return None;
}
let pos = esquerda as i64
+ ((alvo - vetor[esquerda]) as i64
* (direita as i64 - esquerda as i64))
/ denominador;
let pos = pos as usize;
if vetor[pos] == alvo {
return Some(pos);
} else if vetor[pos] < alvo {
esquerda = pos + 1;
} else {
if pos == 0 {
return None;
}
direita = pos - 1;
}
}
None
}
fn main() {
// Vetor uniformemente distribuído — caso ideal
let uniforme: Vec<i64> = (0..100).map(|i| i * 10).collect();
println!("Buscar 670: {:?}", busca_interpolacao(&uniforme, 670)); // Some(67)
println!("Buscar 335: {:?}", busca_interpolacao(&uniforme, 335)); // None
// Vetor menor
let v = vec![10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
println!("\nBuscar 80: {:?}", busca_interpolacao(&v, 80)); // Some(7)
println!("Buscar 35: {:?}", busca_interpolacao(&v, 35)); // None
}
Exemplo de Execução
Buscar 7: Some(3)
Buscar 4: None
Todos os 7: [3, 6]
Primeiro par: Some(1)
Buscar 'uva': Some(2)
Todas 'uva': [2, 4]
Versão com rastreamento comparativo:
fn comparar_buscas(vetor: &[i64], alvo: i64) {
println!("=== Buscando {} em vetor de {} elementos ===\n", alvo, vetor.len());
// Busca linear
let mut passos_linear = 0;
let mut resultado_linear = None;
for (i, &v) in vetor.iter().enumerate() {
passos_linear += 1;
if v == alvo {
resultado_linear = Some(i);
break;
}
}
println!(
"Busca Linear: resultado={:?}, passos={}",
resultado_linear, passos_linear
);
// Busca binária
let mut passos_binaria = 0;
let mut esq = 0usize;
let mut dir = vetor.len();
let mut resultado_binaria = None;
while esq < dir {
passos_binaria += 1;
let meio = esq + (dir - esq) / 2;
if vetor[meio] == alvo {
resultado_binaria = Some(meio);
break;
} else if vetor[meio] < alvo {
esq = meio + 1;
} else {
dir = meio;
}
}
println!(
"Busca Binária: resultado={:?}, passos={}",
resultado_binaria, passos_binaria
);
// Busca por interpolação
let mut passos_interp = 0;
let mut esq = 0usize;
let mut dir = vetor.len() - 1;
let mut resultado_interp = None;
while esq <= dir && alvo >= vetor[esq] && alvo <= vetor[dir] {
passos_interp += 1;
if esq == dir {
if vetor[esq] == alvo {
resultado_interp = Some(esq);
}
break;
}
let denom = vetor[dir] - vetor[esq];
if denom == 0 {
break;
}
let pos = esq + ((alvo - vetor[esq]) as usize * (dir - esq)) / denom as usize;
if vetor[pos] == alvo {
resultado_interp = Some(pos);
break;
} else if vetor[pos] < alvo {
esq = pos + 1;
} else {
if pos == 0 {
break;
}
dir = pos - 1;
}
}
println!(
"Busca Interpolação: resultado={:?}, passos={}",
resultado_interp, passos_interp
);
}
fn main() {
// Vetor uniformemente distribuído de 100 elementos
let vetor: Vec<i64> = (1..=100).collect();
comparar_buscas(&vetor, 73);
println!();
comparar_buscas(&vetor, 7);
}
Variações e Otimizações
1. Busca Linear com Parada Antecipada em Vetor Ordenado
Se o vetor estiver ordenado, podemos parar quando encontrarmos um elemento maior que o alvo:
/// Busca linear otimizada para vetores ordenados.
/// Para de buscar quando encontra elemento maior que o alvo.
fn busca_linear_ordenada<T: Ord>(vetor: &[T], alvo: &T) -> Option<usize> {
for (i, elemento) in vetor.iter().enumerate() {
match elemento.cmp(alvo) {
std::cmp::Ordering::Equal => return Some(i),
std::cmp::Ordering::Greater => return None, // parada antecipada
std::cmp::Ordering::Less => continue,
}
}
None
}
fn main() {
let v = vec![2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
println!("Buscar 8: {:?}", busca_linear_ordenada(&v, &8)); // Some(2)
println!("Buscar 10: {:?}", busca_linear_ordenada(&v, &10)); // None (parou no 12)
println!("Buscar 50: {:?}", busca_linear_ordenada(&v, &50)); // None (parou no 56)
}
2. Busca por Saltos (Jump Search)
Combina busca linear com saltos de tamanho raiz de n, resultando em O(raiz de n):
/// Jump Search — busca por saltos de tamanho √n.
/// Requer vetor ordenado. Complexidade: O(√n).
fn busca_salto<T: Ord>(vetor: &[T], alvo: &T) -> Option<usize> {
let n = vetor.len();
if n == 0 {
return None;
}
// Tamanho do salto: √n
let salto = (n as f64).sqrt() as usize;
let salto = if salto == 0 { 1 } else { salto };
// Fase 1: saltar até encontrar um bloco que possa conter o alvo
let mut inicio = 0;
let mut fim = salto.min(n) - 1;
while vetor[fim] < *alvo {
inicio = fim + 1;
if inicio >= n {
return None;
}
fim = (fim + salto).min(n - 1);
}
// Fase 2: busca linear dentro do bloco
for i in inicio..=fim {
if i >= n {
return None;
}
if vetor[i] == *alvo {
return Some(i);
}
if vetor[i] > *alvo {
return None;
}
}
None
}
fn main() {
let v: Vec<i32> = (0..100).map(|i| i * 3).collect(); // [0, 3, 6, 9, ..., 297]
println!("Tamanho do salto: {}", (v.len() as f64).sqrt() as usize);
println!("Buscar 42: {:?}", busca_salto(&v, &42)); // Some(14)
println!("Buscar 50: {:?}", busca_salto(&v, &50)); // None
}
Visualização do Jump Search:
Vetor: [0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, ...]
Salto = √16 = 4
Alvo = 42
Fase 1 — Saltos:
vetor[3] = 9 < 42 → saltar
vetor[7] = 21 < 42 → saltar
vetor[11] = 33 < 42 → saltar
vetor[15] = 42 ≥ 42 → bloco encontrado [12..15]
Fase 2 — Busca linear no bloco:
vetor[12] = 36 ≠ 42
vetor[13] = 39 ≠ 42
vetor[14] = 42 == 42 → ENCONTRADO!
3. Busca Exponencial
Encontra o intervalo em tempo O(log n) e depois usa busca binária:
/// Busca exponencial — encontra o intervalo e depois usa busca binária.
/// Útil para vetores ordenados onde o elemento provavelmente está no início.
fn busca_exponencial<T: Ord>(vetor: &[T], alvo: &T) -> Option<usize> {
let n = vetor.len();
if n == 0 {
return None;
}
// Verificar o primeiro elemento
if vetor[0] == *alvo {
return Some(0);
}
// Encontrar o intervalo dobrando a posição
let mut limite = 1;
while limite < n && vetor[limite] <= *alvo {
limite *= 2;
}
// Busca binária no intervalo [limite/2, min(limite, n-1)]
let inicio = limite / 2;
let fim = limite.min(n);
match vetor[inicio..fim].binary_search(alvo) {
Ok(pos) => Some(inicio + pos),
Err(_) => None,
}
}
fn main() {
// Vetor grande onde o alvo está perto do início
let v: Vec<i32> = (0..10000).collect();
println!("Buscar 15: {:?}", busca_exponencial(&v, &15)); // Some(15)
println!("Buscar 9999: {:?}", busca_exponencial(&v, &9999)); // Some(9999)
println!("Buscar -1: {:?}", busca_exponencial(&v, &-1)); // None
}
Quando Usar
Busca Linear
- Dados não ordenados: quando não vale a pena ordenar primeiro.
- Vetores pequenos (n < 30): o overhead da busca binária pode superar o benefício.
- Busca por predicado: encontrar o primeiro elemento que satisfaz uma condição complexa.
- Busca única: se vai buscar apenas uma vez, não vale ordenar.
Busca Sentinela
- Loops internos críticos: quando eliminar uma comparação por iteração faz diferença mensurável.
- Sistemas embarcados: ambientes onde cada ciclo conta.
- Vetores mutáveis: requer acesso mutável temporário ao vetor.
Busca por Interpolação
- Dados uniformemente distribuídos: IDs sequenciais, timestamps regulares, valores numéricos uniformes.
- Grandes volumes ordenados: o benefício de O(log log n) vs O(log n) cresce com n.
- Dados numéricos: a fórmula de interpolação requer aritmética sobre os valores.
Evite a busca por interpolação quando:
- Os dados não são numéricos ou não têm distribuição uniforme.
- O vetor é pequeno — busca binária é mais simples e quase tão rápida.
Comparação com Outros Algoritmos
| Característica | Busca Linear | Sentinela | Jump Search | Busca Binária | Interpolação |
|---|---|---|---|---|---|
| Complexidade (média) | O(n) | O(n) | O(√n) | O(log n) | O(log log n)* |
| Pior caso | O(n) | O(n) | O(√n) | O(log n) | O(n) |
| Requer ordenação | Nao | Nao | Sim | Sim | Sim |
| Distribuição uniforme | N/A | N/A | N/A | N/A | Sim |
| Espaço extra | O(1) | O(1) | O(1) | O(1) | O(1) |
| Dados dinâmicos | Sim ✓ | Sim ✓ | Ruim | Ruim | Ruim |
| Simplicidade | Alta ✓ | Média | Média | Média | Baixa |
*O(log log n) apenas para distribuição uniforme.
Tabela Resumo de Todos os Algoritmos de Busca
| Cenário | Algoritmo Recomendado |
|---|---|
| Dados não ordenados, busca única | Busca Linear |
| Dados não ordenados, muitas buscas | Ordenar + Busca Binária |
| Dados ordenados, busca geral | Busca Binária |
| Dados ordenados + uniformes + grandes | Busca por Interpolação |
| Vetor pequeno (n < 30) | Busca Linear |
| Busca com predicado complexo | Busca Linear com position() |
| Verificar existência + posição de inserção | binary_search() do Rust |
Exercícios Práticos
Busca linear genérica com closures: Implemente uma função
buscar_max_porque encontre o elemento que maximiza uma função dada. Por exemplo, encontrar a string mais longa em um vetor de strings. Use closures e a traitFn.Benchmark de buscas: Compare busca linear, busca binária e busca por interpolação em vetores de tamanho 1.000, 10.000 e 100.000. Use
std::time::Instant. Em que tamanho a busca binária começa a vencer consistentemente a linear? E a interpolação, quando supera a binária?Busca em texto: Implemente uma busca linear que encontre todas as posições de uma substring dentro de uma string, sem usar o método
find()da biblioteca padrão. Use apenas iteração sobre bytes ou caracteres.Interpolação adaptativa: Implemente uma busca que comece com interpolação mas, se detectar que a estimativa foi ruim (espaço de busca não reduziu significativamente), mude automaticamente para busca binária. Compare o desempenho com interpolação pura em dados não uniformes.
Veja Também
- Busca Binária em Rust — busca O(log n) para dados ordenados
- Merge Sort em Rust — ordenar dados antes de aplicar busca binária
- Quick Sort em Rust — alternativa de ordenação para preparar busca
- Vec — Vetores Dinâmicos — métodos
contains(),iter().position() - Iterator — Iteradores —
find(),position(),any(),filter() - Option — Valores Opcionais — tipo de retorno natural para buscas