102. slice::partition_point — Binary Search That Just Returns the Index
Reaching for binary_search on a sorted Vec and unwrapping Ok(i) | Err(i) because you only ever wanted the index? slice::partition_point skips the Result ceremony and hands you the position directly.
The binary_search annoyance
binary_search is great when you care whether the value was actually found. But often you don’t — you just want the spot where it would go to keep the slice sorted:
| |
The Ok | Err pattern works, but it’s noisy and obscures the intent. Worse, it doesn’t generalise — what if you want the insertion point for a predicate, not an exact value?
partition_point to the rescue
partition_point takes a predicate and returns the first index where the predicate flips from true to false. On a sorted slice, that’s the insertion point — no Result, no match arms:
| |
The slice still has to be partitioned (all trues before all falses), but for a sorted slice with a < predicate that’s automatic. Internally it’s still O(log n) binary search — same complexity as binary_search, friendlier API.
Insert while keeping sorted
A common use: keep a Vec sorted as you add to it.
| |
Compare that to binary_search(&new_score).unwrap_or_else(|i| i) — same result, more ceremony.
Beyond simple ordering
Because it takes any predicate, partition_point works on any slice partitioned by a property — not just sorted-by-Ord. Sorted by a derived key? Filter by a threshold? Same call:
| |
That second line is a slick trick: partition_point doubles as “count how many elements satisfy the prefix predicate” in O(log n).
When to reach for it
Any time you find yourself writing binary_search(...).unwrap_or_else(|i| i) or match ... { Ok(i) | Err(i) => i }, swap in partition_point. Stable since Rust 1.52 — old enough to use everywhere, fresh enough that plenty of code still does it the noisy way.