Equipe Rust Brasil 12 min de leitura

Busca Binária em Rust

Aprenda Busca Binária em Rust com versões iterativa e recursiva, variantes lower/upper bound, diagramas visuais e análise Big-O.

busca binary-search algoritmos rust

A Busca Binária (binary search) é um dos algoritmos mais fundamentais e eficientes da computação. Ela encontra a posição de um elemento em um vetor ordenado dividindo repetidamente o espaço de busca pela metade. A cada comparação, metade dos elementos restantes é eliminada, resultando em complexidade O(log n) — drasticamente mais rápido que a busca linear O(n).

Para um vetor de 1 milhão de elementos, a busca linear pode fazer até 1.000.000 de comparações. A busca binária precisa de no máximo 20. Para 1 bilhão de elementos, apenas 30 comparações. Essa eficiência exponencial torna a busca binária indispensável em bancos de dados, sistemas de arquivos, compiladores e praticamente qualquer sistema que trabalhe com dados ordenados.

Como Funciona

A busca binária mantém dois ponteiros (esquerda e direita) que definem o espaço de busca. A cada iteração:

  1. Calcula o ponto médio.
  2. Compara o elemento do meio com o alvo.
  3. Se igual, encontrou. Se menor, busca na metade direita. Se maior, busca na metade esquerda.
Buscar o valor 23 no vetor ordenado:

Índice: [0]  [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]  [9]
Valor:   2    5    8   12   16   23   38   56   72   91

=== Iteração 1 ===
esq=0, dir=9, meio=4
vetor[4] = 16

  [ 2    5    8   12   16   23   38   56   72   91]
    esq              meio                       dir
                      16 < 23 → buscar à DIREITA

=== Iteração 2 ===
esq=5, dir=9, meio=7
vetor[7] = 56

  [                       23   38   56   72   91]
                          esq       meio       dir
                                    56 > 23 → buscar à ESQUERDA

=== Iteração 3 ===
esq=5, dir=6, meio=5
vetor[5] = 23

  [                       23   38]
                          esq  dir
                          meio
                          23 == 23 → ENCONTRADO no índice 5!

Total: 3 comparações (log2(10) ≈ 3.3)

Visualização da redução do espaço de busca:

Iteração 1: |████████████████████| 10 elementos
Iteração 2:           |██████████|  5 elementos
Iteração 3:           |████|        2 elementos
Encontrado!           |██|          1 elemento

A cada passo, o espaço é dividido pela metade!

Complexidade

CasoTempoEspaço
MelhorO(1)O(1) iterativo / O(log n) recursivo
MédioO(log n)O(1) iterativo / O(log n) recursivo
PiorO(log n)O(1) iterativo / O(log n) recursivo
  • Melhor caso O(1): o elemento buscado está exatamente no meio do vetor na primeira comparação.
  • Caso médio e pior O(log n): a cada iteração, o espaço de busca é dividido pela metade. Após k iterações, restam n/2^k elementos. Quando n/2^k = 1, temos k = log2(n).
  • Pré-requisito: o vetor DEVE estar ordenado. Se não estiver, a busca binária pode retornar resultados incorretos.
  • Espaço: a versão iterativa usa O(1) de espaço extra. A versão recursiva usa O(log n) na pilha de chamadas.
Tamanho (n)Comparações (log2 n)
1007
1.00010
1.000.00020
1.000.000.00030

Implementação em Rust

Versão Iterativa

/// Busca binária iterativa.
/// Retorna Some(índice) se o elemento for encontrado, None caso contrário.
/// O vetor DEVE estar ordenado em ordem crescente.
fn busca_binaria<T: Ord>(vetor: &[T], alvo: &T) -> Option<usize> {
    let mut esquerda = 0;
    let mut direita = vetor.len();

    while esquerda < direita {
        // Evitar overflow: meio = esquerda + (direita - esquerda) / 2
        let meio = esquerda + (direita - esquerda) / 2;

        match vetor[meio].cmp(alvo) {
            std::cmp::Ordering::Equal => return Some(meio),
            std::cmp::Ordering::Less => esquerda = meio + 1,
            std::cmp::Ordering::Greater => direita = meio,
        }
    }

    None
}

fn main() {
    let numeros = vec![2, 5, 8, 12, 16, 23, 38, 56, 72, 91];

    // Buscar elementos existentes
    println!("Buscar 23: {:?}", busca_binaria(&numeros, &23)); // Some(5)
    println!("Buscar 2:  {:?}", busca_binaria(&numeros, &2));  // Some(0)
    println!("Buscar 91: {:?}", busca_binaria(&numeros, &91)); // Some(9)

    // Buscar elemento inexistente
    println!("Buscar 50: {:?}", busca_binaria(&numeros, &50)); // None

    // Funciona com strings também
    let palavras = vec!["abacate", "banana", "caju", "damasco", "figo"];
    println!("\nBuscar 'caju': {:?}", busca_binaria(&palavras, &"caju")); // Some(2)
    println!("Buscar 'uva':  {:?}", busca_binaria(&palavras, &"uva"));   // None
}

Versão Recursiva

/// Busca binária recursiva.
/// Retorna Some(índice) se encontrado, None caso contrário.
fn busca_binaria_recursiva<T: Ord>(vetor: &[T], alvo: &T) -> Option<usize> {
    busca_recursiva_interna(vetor, alvo, 0, vetor.len())
}

fn busca_recursiva_interna<T: Ord>(
    vetor: &[T],
    alvo: &T,
    esquerda: usize,
    direita: usize,
) -> Option<usize> {
    if esquerda >= direita {
        return None;
    }

    let meio = esquerda + (direita - esquerda) / 2;

    match vetor[meio].cmp(alvo) {
        std::cmp::Ordering::Equal => Some(meio),
        std::cmp::Ordering::Less => busca_recursiva_interna(vetor, alvo, meio + 1, direita),
        std::cmp::Ordering::Greater => busca_recursiva_interna(vetor, alvo, esquerda, meio),
    }
}

fn main() {
    let v = vec![1, 3, 5, 7, 9, 11, 13, 15];
    println!("Buscar 7: {:?}", busca_binaria_recursiva(&v, &7));   // Some(3)
    println!("Buscar 6: {:?}", busca_binaria_recursiva(&v, &6));   // None
}

Usando a Biblioteca Padrão

O Rust oferece o método binary_search() em slices:

fn main() {
    let v = vec![2, 5, 8, 12, 16, 23, 38, 56, 72, 91];

    // binary_search retorna Result<usize, usize>
    // Ok(índice) se encontrado
    // Err(índice) com a posição onde o elemento deveria ser inserido
    match v.binary_search(&23) {
        Ok(pos) => println!("Encontrado 23 na posição {}", pos),
        Err(pos) => println!("23 não encontrado, inserir na posição {}", pos),
    }

    match v.binary_search(&50) {
        Ok(pos) => println!("Encontrado 50 na posição {}", pos),
        Err(pos) => println!("50 não encontrado, inserir na posição {}", pos),
    }

    // binary_search_by — busca com comparador personalizado
    let pares = vec![(1, "um"), (3, "três"), (5, "cinco"), (7, "sete")];
    let resultado = pares.binary_search_by(|item| item.0.cmp(&5));
    println!("\nBuscar chave 5: {:?}", resultado); // Ok(2)

    // binary_search_by_key — busca por campo
    let resultado = pares.binary_search_by_key(&3, |item| item.0);
    println!("Buscar chave 3: {:?}", resultado); // Ok(1)

    // partition_point — encontrar ponto de partição
    let ponto = v.partition_point(|&x| x < 30);
    println!("\nElementos < 30: {:?}", &v[..ponto]);
    println!("Elementos >= 30: {:?}", &v[ponto..]);
}

Exemplo de Execução

Encontrado 23 na posição 5
50 não encontrado, inserir na posição 7

Buscar chave 5: Ok(2)
Buscar chave 3: Ok(1)

Elementos < 30: [2, 5, 8, 12, 16, 23]
Elementos >= 30: [38, 56, 72, 91]

Versão com rastreamento:

fn busca_binaria_rastreada(vetor: &[i32], alvo: i32) -> Option<usize> {
    let mut esquerda = 0;
    let mut direita = vetor.len();
    let mut iteracao = 0;

    println!("Buscando {} em {:?}\n", alvo, vetor);

    while esquerda < direita {
        iteracao += 1;
        let meio = esquerda + (direita - esquerda) / 2;

        println!(
            "  Iteração {}: esq={}, dir={}, meio={}, vetor[meio]={}",
            iteracao, esquerda, direita, meio, vetor[meio]
        );

        match vetor[meio].cmp(&alvo) {
            std::cmp::Ordering::Equal => {
                println!("  → Encontrado na posição {}!", meio);
                return Some(meio);
            }
            std::cmp::Ordering::Less => {
                println!("  → {} < {} → buscar à direita", vetor[meio], alvo);
                esquerda = meio + 1;
            }
            std::cmp::Ordering::Greater => {
                println!("  → {} > {} → buscar à esquerda", vetor[meio], alvo);
                direita = meio;
            }
        }
    }

    println!("  → Não encontrado após {} iterações", iteracao);
    None
}

fn main() {
    let v = vec![2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
    busca_binaria_rastreada(&v, 23);
    println!();
    busca_binaria_rastreada(&v, 50);
}

Variações e Otimizações

1. Lower Bound e Upper Bound

Encontrar a primeira e última posição de um valor em um vetor com duplicatas:

/// Lower bound: encontra o índice do PRIMEIRO elemento >= alvo.
/// Equivalente a std::lower_bound em C++ ou partition_point(|x| x < alvo).
fn lower_bound<T: Ord>(vetor: &[T], alvo: &T) -> usize {
    let mut esquerda = 0;
    let mut direita = vetor.len();

    while esquerda < direita {
        let meio = esquerda + (direita - esquerda) / 2;
        if vetor[meio] < *alvo {
            esquerda = meio + 1;
        } else {
            direita = meio;
        }
    }

    esquerda
}

/// Upper bound: encontra o índice do PRIMEIRO elemento > alvo.
/// Equivalente a std::upper_bound em C++ ou partition_point(|x| x <= alvo).
fn upper_bound<T: Ord>(vetor: &[T], alvo: &T) -> usize {
    let mut esquerda = 0;
    let mut direita = vetor.len();

    while esquerda < direita {
        let meio = esquerda + (direita - esquerda) / 2;
        if vetor[meio] <= *alvo {
            esquerda = meio + 1;
        } else {
            direita = meio;
        }
    }

    esquerda
}

/// Contar quantas vezes um valor aparece no vetor ordenado.
fn contar_ocorrencias<T: Ord>(vetor: &[T], alvo: &T) -> usize {
    let lb = lower_bound(vetor, alvo);
    let ub = upper_bound(vetor, alvo);
    ub - lb
}

/// Encontrar o intervalo [primeiro, último] de um valor.
fn buscar_intervalo<T: Ord>(vetor: &[T], alvo: &T) -> Option<(usize, usize)> {
    let lb = lower_bound(vetor, alvo);
    if lb >= vetor.len() || vetor[lb] != *alvo {
        return None;
    }
    let ub = upper_bound(vetor, alvo);
    Some((lb, ub - 1))
}

fn main() {
    let v = vec![1, 2, 2, 2, 3, 3, 5, 5, 5, 5, 7, 8];
    //           0  1  2  3  4  5  6  7  8  9 10 11

    println!("Vetor: {:?}\n", v);

    println!("lower_bound(2) = {} (primeira posição >= 2)", lower_bound(&v, &2));
    println!("upper_bound(2) = {} (primeira posição > 2)", upper_bound(&v, &2));
    println!("Ocorrências de 2: {}", contar_ocorrencias(&v, &2));
    println!("Intervalo de 2: {:?}", buscar_intervalo(&v, &2));

    println!();
    println!("lower_bound(5) = {}", lower_bound(&v, &5));
    println!("upper_bound(5) = {}", upper_bound(&v, &5));
    println!("Ocorrências de 5: {}", contar_ocorrencias(&v, &5));
    println!("Intervalo de 5: {:?}", buscar_intervalo(&v, &5));

    println!();
    println!("lower_bound(4) = {} (posição de inserção para 4)", lower_bound(&v, &4));
    println!("Intervalo de 4: {:?}", buscar_intervalo(&v, &4));
}

2. Posição de Inserção (Search Insert Position)

Encontrar onde um elemento deveria ser inserido para manter o vetor ordenado:

/// Encontra a posição onde `alvo` deveria ser inserido para manter a ordem.
/// Se o alvo já existe, retorna a posição dele.
fn posicao_insercao<T: Ord>(vetor: &[T], alvo: &T) -> usize {
    let mut esquerda = 0;
    let mut direita = vetor.len();

    while esquerda < direita {
        let meio = esquerda + (direita - esquerda) / 2;
        if vetor[meio] < *alvo {
            esquerda = meio + 1;
        } else {
            direita = meio;
        }
    }

    esquerda
}

/// Vetor ordenado com inserção eficiente usando busca binária.
struct VetorOrdenado<T: Ord> {
    dados: Vec<T>,
}

impl<T: Ord> VetorOrdenado<T> {
    fn novo() -> Self {
        VetorOrdenado { dados: Vec::new() }
    }

    fn inserir(&mut self, valor: T) {
        let pos = posicao_insercao(&self.dados, &valor);
        self.dados.insert(pos, valor);
    }

    fn contem(&self, valor: &T) -> bool {
        self.dados.binary_search(valor).is_ok()
    }

    fn como_slice(&self) -> &[T] {
        &self.dados
    }
}

fn main() {
    let v = vec![1, 3, 5, 7, 9];
    println!("Vetor: {:?}\n", v);

    for alvo in [0, 4, 6, 10] {
        let pos = posicao_insercao(&v, &alvo);
        println!("Inserir {} na posição {} → mantém ordenado", alvo, pos);
    }

    println!("\n--- Vetor Ordenado ---");
    let mut vo = VetorOrdenado::novo();
    for x in [5, 2, 8, 1, 9, 3] {
        vo.inserir(x);
        println!("Inserir {} → {:?}", x, vo.como_slice());
    }
    println!("Contém 5? {}", vo.contem(&5));
    println!("Contém 4? {}", vo.contem(&4));
}

3. Busca Binária em Resposta (Binary Search on Answer)

Técnica poderosa para problemas de otimização: buscar sobre o espaço de respostas possíveis.

/// Exemplo: encontrar a raiz quadrada inteira de um número.
/// Maior x tal que x * x <= n.
fn raiz_quadrada_inteira(n: u64) -> u64 {
    if n <= 1 {
        return n;
    }

    let mut esquerda: u64 = 1;
    let mut direita: u64 = n;
    let mut resultado: u64 = 1;

    while esquerda <= direita {
        let meio = esquerda + (direita - esquerda) / 2;

        // Usar meio <= n / meio para evitar overflow (em vez de meio * meio <= n)
        if meio <= n / meio {
            resultado = meio;
            esquerda = meio + 1;
        } else {
            direita = meio - 1;
        }
    }

    resultado
}

/// Exemplo: verificar se é possível dividir o vetor em k partes
/// onde a soma máxima de cada parte não excede `limite`.
fn pode_dividir(vetor: &[i64], k: usize, limite: i64) -> bool {
    let mut partes = 1;
    let mut soma_atual = 0;

    for &valor in vetor {
        if valor > limite {
            return false; // Um único elemento já excede o limite
        }
        soma_atual += valor;
        if soma_atual > limite {
            partes += 1;
            soma_atual = valor;
            if partes > k {
                return false;
            }
        }
    }

    true
}

/// Minimizar a soma máxima ao dividir o vetor em k partes.
fn minimizar_soma_maxima(vetor: &[i64], k: usize) -> i64 {
    let mut esquerda: i64 = *vetor.iter().max().unwrap();
    let mut direita: i64 = vetor.iter().sum();

    while esquerda < direita {
        let meio = esquerda + (direita - esquerda) / 2;
        if pode_dividir(vetor, k, meio) {
            direita = meio;
        } else {
            esquerda = meio + 1;
        }
    }

    esquerda
}

fn main() {
    // Raiz quadrada
    for n in [0, 1, 4, 8, 16, 25, 100, 1000000] {
        println!("sqrt({}) = {}", n, raiz_quadrada_inteira(n));
    }

    // Minimizar soma máxima
    println!();
    let vetor = vec![7, 2, 5, 10, 8];
    let k = 2;
    let resultado = minimizar_soma_maxima(&vetor, k);
    println!(
        "Vetor {:?}, dividir em {} partes: soma máxima mínima = {}",
        vetor, k, resultado
    );
}

Quando Usar

A Busca Binária e adequada nos seguintes cenários:

  • Busca em dados ordenados: sempre que o vetor estiver ordenado (ou puder ser ordenado previamente), a busca binária é exponencialmente mais rápida que a busca linear.
  • Múltiplas consultas: se você fará muitas buscas no mesmo vetor, vale ordenar uma vez em O(n log n) e fazer cada busca em O(log n), em vez de O(n) por busca linear.
  • Binary Search on Answer: para problemas de otimização onde a resposta é monótona (se funciona para x, funciona para x+1), use busca binária no espaço de respostas.
  • Lower/Upper bound: encontrar posições de inserção, contar ocorrências, buscar intervalos.
  • Verificação de propriedades monótonas: qualquer predicado que mude de falso para verdadeiro (ou vice-versa) ao longo de uma sequência ordenada.

Evite a Busca Binária quando:

  • Os dados não estiverem ordenados e haverá apenas uma consulta — busca linear é mais simples.
  • O vetor for muito pequeno (n < 10) — busca linear pode ser mais rápida por ter menos overhead.
  • Os dados mudarem frequentemente — manter o vetor ordenado pode custar mais que busca linear.

Comparação com Outros Algoritmos

CaracterísticaBusca BináriaBusca LinearBusca por InterpolaçãoHash Table
ComplexidadeO(log n)O(n)O(log log n)*O(1)*
Pré-requisitoOrdenadoNenhumOrd. + uniformeHash function
Espaço extraO(1)O(1)O(1)O(n)
Dados dinâmicosRuimBom ✓RuimBom ✓
Cache-friendlyRazoávelSim ✓NãoNão
Pior casoO(log n) ✓O(n)O(n)O(n)

*A busca por interpolação é O(log log n) para dados uniformemente distribuídos. Hash table é O(1) amortizado, mas O(n) no pior caso.

Exercícios Práticos

  1. Busca em vetor rotacionado: Um vetor ordenado foi rotacionado (ex: [4, 5, 6, 7, 0, 1, 2]). Implemente uma busca binária modificada que encontre um elemento em O(log n) nesse vetor. Dica: identifique qual metade está ordenada.

  2. Pico de montanha: Dado um vetor que primeiro cresce e depois decresce (ex: [1, 3, 8, 12, 4, 2]), encontre o elemento máximo em O(log n) usando busca binária.

  3. Primeira posição de verdadeiro: Dada uma função monótona f(i) que retorna false para i < k e true para i >= k, encontre k usando busca binária. Implemente e teste com f(i) = vetor[i] >= alvo.

  4. Mediana de dois vetores ordenados: Dados dois vetores ordenados de tamanhos m e n, encontre a mediana combinada em O(log(min(m, n))) usando busca binária. Este é um clássico problema de entrevista.

Veja Também