Exercícios de Rust

Binary Search in Rust

Find a value in a sorted slice by halving the search range at every step.

Iniciante
3 min de leitura
1 exemplo executável

O que você vai aprender

low, high and middle
Returning Option<usize>
Why it is fast

Executar código →

Search for 23

164

235

386

567

Found at index 5 after three steps.

Halve the range each step

Binary search looks at the middle of a sorted list and throws away the half that cannot contain the target. Each step halves the work, so it is very fast on large lists.

low and high mark the part that is still being searched. The function returns Some(index) when the target is found and None when the range becomes empty. low + (high - low) / 2 finds the middle without overflow.

Pontos-chave

The list must be sorted.
Each step throws away half.
None means the value is not there.

Exemplo executável de Rust

Rust

Executar código →

main.rs

fn binary_search(items: &[i32], target: i32) -> Option<usize> {
    let mut low = 0;
    let mut high = items.len();
    while low < high {
        let middle = low + (high - low) / 2;
        if items[middle] == target {
            return Some(middle);
        } else if items[middle] < target {
            low = middle + 1;
        } else {
            high = middle;
        }
    }
    None
}

fn main() {
    let sorted = [2, 5, 8, 12, 16, 23, 38, 56];
    println!("{:?}", binary_search(&sorted, 23));
    println!("{:?}", binary_search(&sorted, 7));
}

Gerar um botão Run para este exemplo Resultado da execução

Some(5)
None

Pratique

Abra o exemplo no compilador online, mude um valor ou adicione uma linha e tente prever a saída antes de executar. Depois quebre o código de propósito e leia a mensagem do compilador.

Terminou esta lição?

Marque como aprendida para acompanhar seu progresso.

Próxima: Structs →

Pratique com um desafio

Use o conteúdo desta lição para resolver um problema real. Cada desafio roda no navegador, com testes instantâneos e uma revisão por IA.

Todos os desafios