Rust-Übungen

Binary Search in Rust

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

Einsteiger
3 Min. Lesezeit
1 ausführbares Beispiel

Das lernst du

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

Code ausführen →

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.

Das Wichtigste

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

Ausführbares Rust-Beispiel

Rust

Code ausführen →

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

Run-Button für dieses Beispiel erstellen Ergebnis der Ausführung

Some(5)
None

Üben

Öffne das Beispiel im Online-Compiler, ändere einen Wert oder füge eine Zeile hinzu und sage die Ausgabe voraus, bevor du es ausführst. Bring den Code danach absichtlich zum Scheitern und lies die Meldung des Compilers.

Lektion fertig?

Markiere sie als gelernt, um deinen Fortschritt zu verfolgen.

Weiter: Structs →

Mit einer Challenge üben

Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.

Alle Challenges