Esercizi di Rust

Binary Search in Rust

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

Principiante
3 min di lettura
1 esempio eseguibile

Cosa imparerai

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

Esegui il codice →

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.

Punti chiave

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

Esempio Rust eseguibile

Rust

Esegui il codice →

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));
}

Crea un pulsante Run per questo esempio Risultato dell'esecuzione

Some(5)
None

Esercitati

Apri l'esempio nel compilatore online, cambia un valore o aggiungi una riga e prova a prevedere l'output prima di eseguirlo. Poi rompi il codice di proposito e leggi il messaggio del compilatore.

Hai finito questa lezione?

Segnala come imparata per tenere traccia dei tuoi progressi.

Prossima: Structs →

Esercitati con una sfida

Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.

Tutte le sfide