Rust Practice Exercises

Binary Search in Rust

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

Beginner
3 min read
1 runnable example

What you'll learn

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

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

Key points

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

Runnable Rust example

Rust

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

Get a Run button for this example Result of running the code

Some(5)
None

Practice

Open the example in the online compiler, change a value or add a line, and predict the output before you run it. Then break the code on purpose and read the compiler's message.

Finished this lesson?

Mark it as learned to track your progress.

Next: Structs →

Practice with a challenge

Use what this lesson covers to solve a real problem. Each challenge runs in your browser with instant tests and an AI review.

All challenges