Binary Search on Sorted Vectors

Once a Vec<T> (or slice [T]) is sorted in ascending order, .binary_search(), .binary_search_by(), .binary_search_by_key(), and .partition_point() locate elements or insertion boundaries in $O(\log n)$ time.

Return Value: Result<usize, usize>

pub fn binary_search(&self, x: &T) -> Result<usize, usize>
where
    T: Ord

Unlike a boolean .contains(), .binary_search(&x) returns rich index information in both the Ok and Err variants:

• Ok(found_index): An element equal to x was found at v[found_index]. (If duplicate elements exist, any matching index may be returned.)
• Err(insert_index): x is not present, and inserting x at v.insert(insert_index, x) will preserve the sorted order of the vector.

Sorted Vec:  [ 10,   20,   30,   40 ]
Index:          0     1     2     3

v.binary_search(&30) ──> Ok(2)   (found at index 2)
v.binary_search(&25) ──> Err(2)  (not found; belongs at index 2 before 30)
v.binary_search(&99) ──> Err(4)  (not found; belongs at index 4 at the end)

fn main() {
    let mut timestamps = vec![100_u64, 200, 300, 400];

    println!("Search 300: {:?}", timestamps.binary_search(&300));
    println!("Search 250: {:?}", timestamps.binary_search(&250));

    // Insert 250 at its exact sorted position using the `Err(idx)` index:
    if let Err(idx) = timestamps.binary_search(&250) {
        timestamps.insert(idx, 250);
    }
    println!("After sorted insert: {timestamps:?}");
}

Search 300: Ok(2)
Search 250: Err(2)
After sorted insert: [100, 200, 250, 300, 400]

Searching Structs by Field with binary_search_by_key

When a Vec<Struct> is sorted by a specific key field, use .binary_search_by_key(&target_key, |item| item.key) to search without constructing a dummy struct:

#[derive(Debug)]
struct User {
    id: u32,
    username: &'static str,
}

fn main() {
    let users = vec![
        User { id: 101, username: "alice" },
        User { id: 205, username: "bob" },
        User { id: 310, username: "carol" },
    ];

    if let Ok(idx) = users.binary_search_by_key(&205, |u| u.id) {
        println!("Found user 205: {:?}", users[idx]);
    }
}

Found user 205: User { id: 205, username: "bob" }

Finding Lower and Upper Bounds with partition_point()

When a sorted vector contains duplicate values, .binary_search(&x) returns any matching index. To find the exact first index $\ge x$ (lower_bound in C++) or the first index $> x$ (upper_bound), use v.partition_point(pred) in $O(\log n)$ time:

Boundary	Expression on Sorted v	Meaning
Lower bound (first index $\ge x$)	v.partition_point(|elem| *elem < x)	Start of range of elements equal to x
Upper bound (first index $> x$)	v.partition_point(|elem| *elem <= x)	Exclusive end of range of elements equal to x

fn equal_range(sorted: &[i32], target: i32) -> std::ops::Range<usize> {
    let start = sorted.partition_point(|&x| x < target);
    let end = sorted.partition_point(|&x| x <= target);
    start..end
}

fn main() {
    let data = [10, 20, 20, 20, 30, 40];
    let range = equal_range(&data, 20);
    println!("Indices of 20: {range:?} -> {:?}", &data[range]);
}

Indices of 20: 1..4 -> [20, 20, 20]