--- title: "Busca Linear e Interpolação em Rust" url: "https://rustlang.com.br/algoritmos/busca-em-largura-profundidade/" markdown_url: "https://rustlang.com.br/algoritmos/busca-em-largura-profundidade.MD" description: "Aprenda Busca Linear, Busca Sentinela e Busca por Interpolação em Rust com diagramas visuais, análise Big-O e comparações." date: "2026-02-24" author: "Equipe Rust Brasil" --- # Busca Linear e Interpolação em Rust Aprenda Busca Linear, Busca Sentinela e Busca por Interpolação em Rust com diagramas visuais, análise Big-O e comparações. 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](/algoritmos/binary-search/): 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: ```text 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: ```text 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: ```text 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: ```text 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 ```rust /// Busca linear genérica. /// Retorna Some(índice) do primeiro elemento igual ao alvo, ou None. /// Funciona em vetores não ordenados. fn busca_linear(vetor: &[T], alvo: &T) -> Option { 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(vetor: &[T], alvo: &T) -> Vec { 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(vetor: &[T], predicado: F) -> Option 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 ```rust /// Busca sentinela — elimina verificação de limites no loop. /// Nota: requer vetor mutável temporariamente. fn busca_sentinela(vetor: &mut Vec, alvo: i32) -> Option { 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 ```rust /// 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 { 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 = (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 ```text 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: ```rust 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 = (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: ```rust /// Busca linear otimizada para vetores ordenados. /// Para de buscar quando encontra elemento maior que o alvo. fn busca_linear_ordenada(vetor: &[T], alvo: &T) -> Option { 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): ```rust /// Jump Search — busca por saltos de tamanho √n. /// Requer vetor ordenado. Complexidade: O(√n). fn busca_salto(vetor: &[T], alvo: &T) -> Option { 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 = (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: ```text 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: ```rust /// 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(vetor: &[T], alvo: &T) -> Option { 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 = (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](/algoritmos/binary-search/) | 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 1. **Busca linear genérica com closures:** Implemente uma função `buscar_max_por` que 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 trait `Fn`. 2. **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? 3. **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. 4. **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](/algoritmos/binary-search/) — busca O(log n) para dados ordenados - [Merge Sort em Rust](/algoritmos/merge-sort/) — ordenar dados antes de aplicar busca binária - [Quick Sort em Rust](/algoritmos/quick-sort/) — alternativa de ordenação para preparar busca - [Vec — Vetores Dinâmicos](/stdlib/vec/) — métodos `contains()`, `iter().position()` - [Iterator — Iteradores](/stdlib/iterator/) — `find()`, `position()`, `any()`, `filter()` - [Option — Valores Opcionais](/stdlib/option/) — tipo de retorno natural para buscas