Ejercicios de Rust

Binary Search in Rust

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

Principiante
3 min de lectura
1 ejemplo ejecutable

Lo que aprenderás

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

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

Puntos clave

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

Ejemplo ejecutable de Rust

Rust

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

Obtén un botón Run para este ejemplo Resultado de ejecutar el código

Some(5)
None

Practica

Abre el ejemplo en el compilador online, cambia un valor o añade una línea y predice la salida antes de ejecutarlo. Después rompe el código a propósito y lee el mensaje del compilador.

¿Terminaste esta lección?

Márcala como aprendida para seguir tu progreso.

Siguiente: Structs →

Practica con un reto

Usa lo que cubre esta lección para resolver un problema real. Cada reto se ejecuta en el navegador, con pruebas al instante y una revisión de IA.

Todos los retos