Skip to content

slice::binary_search

slice methods · Collections

Level: reference · for working programmers

One line: Find a value in a sorted slice in O(log n) — and, when it is absent, learn where it would go.

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

Stable since 1.0.0.

Ok(i) means the value is at index i. Err(i) means it is absent, and i is the index it would have to be inserted at to keep the slice sorted — which is why the return type is a Result and not an Option: the failure case carries an answer. v.insert(i, x) after an Err(i) keeps a vector sorted.

Two rules:

  • The slice must already be sorted, ascending by Ord. On an unsorted slice the result is unspecified — not an error, not a panic, just a number that happens to fall out of the halving. Nothing checks.
  • Duplicates: any matching index. With [1, 2, 2, 2, 3] and &2 you may get 1, 2 or 3. For the first or last occurrence use partition_point ↗ with the right predicate.

binary_search_by and binary_search_by_key take a comparison closure and a key, mirroring the sort_by / sort_by_key pair — sort and search have to agree on the order.

Example

slice_binary_search.rs in full — pasted here by tools/run_examples.py from the file CI compiles and runs.

fn main() {
    let sorted = [1, 3, 5, 7, 9];
    println!("{:?}", sorted.binary_search(&5));
    println!("{:?}  <- absent; 4 would go at index 2", sorted.binary_search(&4));
    println!("{:?}  <- absent; past the end", sorted.binary_search(&100));

    // Err carries the insertion point, so this keeps a Vec sorted.
    let mut v = vec![1, 3, 5, 7, 9];
    for x in [4, 0, 10] {
        let at = v.binary_search(&x).unwrap_or_else(|i| i);
        v.insert(at, x);
    }
    println!("{v:?}");

    // On an unsorted slice the answer is unspecified: not wrong, not an error.
    let unsorted = [9, 1, 5, 3, 7];
    println!("{:?}  <- 5 IS in there, at index 2", unsorted.binary_search(&5));

    // Duplicates: any one of the matching indices may come back.
    let dups = [1, 2, 2, 2, 3];
    println!("{:?}", dups.binary_search(&2));
    println!("first 2 at {}", dups.partition_point(|&x| x < 2));
    println!("past the last 2 at {}", dups.partition_point(|&x| x <= 2));
}

Verified output of slice_binary_search.rs — regenerated by tools/run_examples.py, never hand-typed.

Ok(2)
Err(2)  <- absent; 4 would go at index 2
Err(5)  <- absent; past the end
[0, 1, 3, 4, 5, 7, 9, 10]
Err(4)  <- 5 IS in there, at index 2
Ok(3)
first 2 at 1
past the last 2 at 4

See also

slice::binary_search in the standard library ↗