Weekly Rust Trivia is a problem-oriented series of articles that assist developers while learning Rust. Every article solves simple, everyday development tasks using the Rust standard library or leveraging popular and proven crates.

Question: How to implement binary search in Rust?

All we need to implement binary search in Rust is to bring the cmp module into scope. The cmp::Ordering enum and the cmp::Ord trait provide everything required to implement a generic binary search supporting all types implementing the Ord trait.

RUST 
use std::cmp::Ordering;

fn binary_search<T: Ord>(arr: &[T], desired: &T) -> Option<usize> {
    let mut low = 0;
    let mut high = arr.len();

    while low < high {
        let mid = low + (high - low) / 2;

        match arr[mid].cmp(desired) {
            Ordering::Less => low = mid + 1,
            Ordering::Greater => high = mid,
            Ordering::Equal => return Some(mid),
        }
    }
    None
}

The binary_search function takes in a sorted slice arr and a desired value desired. Binary search only works if the slice is sorted. The function uses generics to constrain the type T to only those that implement the Ord trait, which enables the use of the cmp method to compare values. The function sets the initial low and high indices to 0 and arr.len(), respectively. The search range is half-open (high is exclusive), which keeps the code free from integer underflows for empty slices or when the desired value is smaller than the first element. We also compute the midpoint as low + (high - low) / 2 instead of (low + high) / 2 to avoid an integer overflow for huge slices.

It then enters a while loop where it continually computes the midpoint of the current range and compares the value at that index to the desired value. Based on the comparison result, it either moves the low or high index, or returns the index of the found element if it matches the desired value. If the desired value is not found, the function returns None.

We can use the binary_search function as demonstrated here:

RUST 
fn main() {
    let arr = vec![1, 2, 3, 4, 5, 6, 7, 8, 9];
    let look_for = 6;
    let result = binary_search(&arr, &look_for);

    match result {
        Some(index) => println!("Found {look_for} at index {index}"),
        None => println!("{look_for} not found"),
    }
}

If you want to learn more about the match expression, check out how to use pattern matching .