Skip to content
Tutorials Center
My learning

Topics

Rust Reference ยท Collections

Rust binary_search and partition_point

Reference for Rust slice binary_search, binary_search_by, binary_search_by_key and partition_point: Ok/Err results, insertion points and sorted-input rules.

binary_search finds an element in a sorted slice in O(log n) steps by repeatedly halving the search range. It returns a Result<usize, usize>: Ok(index) when the value is present, and Err(index) with the position where it could be inserted to keep the slice sorted.

partition_point answers a related question: given a slice that is split into a block of elements satisfying a predicate followed by a block that does not, where is the boundary? It is the building block for lower-bound and upper-bound style queries.

Rust
let v = [1, 3, 5, 7];
assert_eq!(v.binary_search(&5), Ok(2));
assert_eq!(v.binary_search(&4), Err(2));

Try it

Rust Finding and inserting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Rust By key and partition_point

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Syntax

Rust
impl<T> [T] {
    pub fn binary_search(&self, x: &T) -> Result<usize, usize> where T: Ord;
    pub fn binary_search_by<F: FnMut(&T) -> Ordering>(&self, f: F) -> Result<usize, usize>;
    pub fn binary_search_by_key<B: Ord, F: FnMut(&T) -> B>(&self, b: &B, f: F) -> Result<usize, usize>;
    pub fn partition_point<P: FnMut(&T) -> bool>(&self, pred: P) -> usize;
}
Name Description
x The value to look for.
f (by) Compares an element with the target: return Less if the element is before the target, Greater if after.
b, f (by key) A target key and a function that extracts the key from each element.
pred true for the leading block of elements, false for the rest.

Returns: Ok(i) with the index of a match, or Err(i) with the insertion point. partition_point returns the index of the first element for which pred is false, or len if all satisfy it.

Edge cases: no panic occurs for unsorted input, but the result is unspecified (still memory safe). An empty slice gives Err(0).

Usage notes

  • The slice must already be sorted by the same ordering you search with. Sort first with sort, or the answer is meaningless.
  • Duplicates: if several elements match, which index you get is unspecified. Use partition_point twice, as in the example, for first and last positions.
  • Err(i) is directly usable as an index for Vec::insert, which makes a sorted vector easy to maintain. For heavy insert workloads, BTreeSet is a better fit.
  • The predicate in partition_point must be monotonic: all true first, then all false. A mixed slice gives an unspecified result.
  • Floats: f64 is not Ord, so use binary_search_by with total_cmp or partial_cmp.
  • Cost: O(log n) comparisons, versus O(n) for iter().position(..). It pays off from a few dozen elements upward, and needs random access, so it does not apply to linked lists.
  • Search by a borrowed key: with Vec<String>, v.binary_search_by(|s| s.as_str().cmp("bob")) avoids allocating a String to compare.
  • Related one-liners: contains is a linear scan; HashSet gives O(1) lookups when order is irrelevant.