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.
let v = [1, 3, 5, 7]; assert_eq!(v.binary_search(&5), Ok(2)); assert_eq!(v.binary_search(&4), Err(2));
Try it
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.
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
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_pointtwice, as in the example, for first and last positions. Err(i)is directly usable as an index forVec::insert, which makes a sorted vector easy to maintain. For heavy insert workloads,BTreeSetis a better fit.- The predicate in
partition_pointmust be monotonic: alltruefirst, then allfalse. A mixed slice gives an unspecified result. - Floats:
f64is notOrd, so usebinary_search_bywithtotal_cmporpartial_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 aStringto compare. - Related one-liners:
containsis a linear scan;HashSetgives O(1) lookups when order is irrelevant.