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:

1
2
3
4
5
6
7
8
9

let nums = vec![1, 3, 5, 7, 9, 11];
let target = 6;

// Awkward: collapse Ok and Err to a single index.
let pos = match nums.binary_search(&target) {
    Ok(i) | Err(i) => i,
};

assert_eq!(pos, 3);

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:

1
2
3
4
5

let nums = vec![1, 3, 5, 7, 9, 11];

let pos = nums.partition_point(|&x| x < 6);

assert_eq!(pos, 3); // 6 would slot between 5 and 7

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.

1
2
3
4
5
6
7

let mut leaderboard = vec![10, 25, 40, 70];
let new_score = 33;

let pos = leaderboard.partition_point(|&x| x < new_score);
leaderboard.insert(pos, new_score);

assert_eq!(leaderboard, [10, 25, 33, 40, 70]);

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

struct Event { day: u32, name: &'static str }

let log = vec![
    Event { day: 1, name: "boot"   },
    Event { day: 2, name: "login"  },
    Event { day: 5, name: "deploy" },
    Event { day: 7, name: "alert"  },
    Event { day: 9, name: "reboot" },
];

// First event on or after day 5.
let i = log.partition_point(|e| e.day < 5);
assert_eq!(log[i].name, "deploy");

// Number of events strictly before day 5.
assert_eq!(log.partition_point(|e| e.day < 5), 2);

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.