---
title: "Busca Binária em Rust"
url: "https://rustlang.com.br/algoritmos/binary-search/"
markdown_url: "https://rustlang.com.br/algoritmos/binary-search.MD"
description: "Aprenda Busca Binária em Rust com versões iterativa e recursiva, variantes lower/upper bound, diagramas visuais e análise Big-O."
date: "2026-02-24"
author: "Equipe Rust Brasil"
---

# 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.


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.

```text
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:

```text
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

| Caso | Tempo | Espaço |
|------|-------|--------|
| Melhor | O(1) | O(1) iterativo / O(log n) recursivo |
| Médio | O(log n) | O(1) iterativo / O(log n) recursivo |
| Pior | O(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) |
|---|---|
| 100 | 7 |
| 1.000 | 10 |
| 1.000.000 | 20 |
| 1.000.000.000 | 30 |

## Implementação em Rust

### Versão Iterativa

```rust
/// 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

```rust
/// 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:

```rust
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

```text
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:

```rust
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:

```rust
/// 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:

```rust
/// 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.

```rust
/// 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ística | Busca Binária | [Busca Linear](/algoritmos/busca-em-largura-profundidade/) | [Busca por Interpolação](/algoritmos/busca-em-largura-profundidade/) | Hash Table |
|---|---|---|---|---|
| Complexidade | O(log n) | O(n) | O(log log n)* | O(1)* |
| Pré-requisito | Ordenado | Nenhum | Ord. + uniforme | Hash function |
| Espaço extra | O(1) | O(1) | O(1) | O(n) |
| Dados dinâmicos | Ruim | Bom ✓ | Ruim | Bom ✓ |
| Cache-friendly | Razoável | Sim ✓ | Não | Não |
| Pior caso | O(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

- [Busca Linear e Interpolação](/algoritmos/busca-em-largura-profundidade/) — alternativas para dados não ordenados ou uniformemente distribuídos
- [Merge Sort em Rust](/algoritmos/merge-sort/) — ordenação necessária antes da busca binária
- [Quick Sort em Rust](/algoritmos/quick-sort/) — outra forma de ordenar antes de buscar
- [Vec — Vetores Dinâmicos](/stdlib/vec/) — estrutura principal para busca
- [Slice — Fatias de Memória](/stdlib/slice/) — métodos `binary_search()`, `partition_point()`
- [Result — Tratamento de Erros](/stdlib/result/) — tipo de retorno de `binary_search()`
- [Option — Valores Opcionais](/stdlib/option/) — representação de busca com/sem resultado