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 bringing the cmp module into scope. The cmp::Ordering enum and the cmd::Ord trait provide everything required to implement a generic binary search supporting all types implementing the Ord trait.

use std::cmp::Ordering;

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

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

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

The binary_search function takes in an array arr and a desired value desired. 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() - 1, respectively.

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:

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 {} at index {}", &look_for, index),
        None => println!("{} not found", &look_for),
    }
}