Exercices Rust

Binary Search in Rust

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

Débutant
3 min de lecture
1 exemple exécutable

Ce que vous allez apprendre

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

Exécuter le code →

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.

Points clés

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

Exemple Rust exécutable

Rust

Exécuter le code →

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

Obtenir un bouton Run pour cet exemple Résultat de l'exécution

Some(5)
None

S'entraîner

Ouvrez l'exemple dans le compilateur en ligne, modifiez une valeur ou ajoutez une ligne, et devinez la sortie avant de l'exécuter. Cassez ensuite le code exprès et lisez le message du compilateur.

Leçon terminée ?

Marquez-la comme apprise pour suivre votre progression.

Suivante : Structs →

S'entraîner avec un défi

Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.

Tous les défis