Pesquisa em Rust: encontre o índice de um elemento de array com máxima performance

Introdução: Por que pesquisar um índice em Rust não é simplesmente "encontrar e retornar"?

Todo desenvolvedor que migra para Rust vindo de Python ou JavaScript, mais cedo ou mais tarde, se pergunta: "Como faço para encontrar o índice de um elemento em um array ou vetor?" Em Python, isso é feito com uma linha list.index(element), em JavaScript — array.indexOf(element). Mas Rust, como um verdadeiro perfeccionista, oferece não um, mas vários métodos, cada um com suas nuances de performance e segurança.

Vamos entender como encontrar o índice de um elemento em coleções Rust (arrays, vetores e slices) de forma que o código seja não apenas correto, mas também rápido. Afinal, em programação de sistemas, cada nanossegundo conta!

Base: métodos principais de pesquisa de índice em Rust

Na biblioteca padrão do Rust, existem dois "principais jogadores" para pesquisa de índice: position() e rposition(). Eles estão disponíveis para qualquer iterador, e portanto para arrays, vetores e slices.

Método position(): pesquisa da esquerda para a direita

position() recebe uma closure e retorna Option<usize> — o índice do primeiro elemento que satisfaz a condição, ou None se tal elemento não for encontrado.

fn main() {\n    let numbers = vec![10, 20, 30, 40, 50];\n    \n    // Procurando a primeira ocorrência do número 30\n    let index = numbers.iter().position(|&x| x == 30);\n    \n    match index {\n        Some(i) => println!("Índice do número 30: {}", i), // Saída: 2\n        None => println!("Elemento não encontrado"),\n    }\n}\n

Observe: chamamos iter() antes de position(). Isso é importante, pois position() é um método da trait Iterator, e não da própria coleção.

Método rposition(): pesquisa da direita para a esquerda

Se você precisa do último índice de ocorrência de um elemento, use rposition(). Ele funciona de forma análoga, mas percorre a coleção do final:

fn main() {\n    let data = vec!['a', 'b', 'c', 'b', 'a'];\n    \n    // Encontrando a última ocorrência de 'b'\n    let last_b = data.iter().rposition(|&c| c == 'b');\n    \n    println!("Último 'b' no índice: {:?}", last_b); // Some(3)\n}\n

Uma limitação importante: rposition() funciona apenas com coleções que suportam travessia bidirecional (trait DoubleEndedIterator). Felizmente, todas as coleções padrão do Rust atendem a esse requisito.

Comparação de performance: position() vs iteração manual

Muitos iniciantes escrevem loops manualmente, pensando que é mais rápido. Vamos verificar essa suposição na prática.

Considere duas abordagens para pesquisar o índice de um elemento em um vetor de 1 milhão de números inteiros:

use std::time::Instant;\n\nfn main() {\n    let large_vec: Vec<i32> = (0..1_000_000).collect();\n    let target = 999_999;\n    \n    // Método 1: position()\n    let start = Instant::now();\n    let pos1 = large_vec.iter().position(|&x| x == target);\n    let duration1 = start.elapsed();\n    println!("position(): {:?}, tempo: {:?}", pos1, duration1);\n    \n    // Método 2: loop manual\n    let start = Instant::now();\n    let mut pos2 = None;\n    for (i, &val) in large_vec.iter().enumerate() {\n        if val == target {\n            pos2 = Some(i);\n            break;\n        }\n    }\n    let duration2 = start.elapsed();\n    println!("Loop manual: {:?}, tempo: {:?}", pos2, duration2);\n}\n

Os resultados em processadores modernos geralmente mostram que position() é tão rápido quanto o loop manual, e às vezes mais rápido devido às otimizações internas do compilador Rust (LLVM). Conclusão: use position() — é idiomático, seguro e não perde em velocidade.

Busca binária: quando os dados estão ordenados

Se sua coleção estiver ordenada, você deve usar binary_se