Search

Binary searching a slice of structs by one field? Don’t hand-roll a .cmp() closure and risk flipping the comparison — project the key and let the stdlib do the rest.

You have a slice sorted by some field and want to find an element by that field. The reflex is binary_search_by with a closure that spells out the comparison — and it’s easy to get the argument order backwards, which silently breaks the search:

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

#[derive(Debug, PartialEq)]
struct Employee {
    id: u32,
    name: &'static str,
}

let staff = [
    Employee { id: 3,  name: "Ada" },
    Employee { id: 7,  name: "Bo"  },
    Employee { id: 12, name: "Cy"  },
];

// The awkward way — you write (and can mis-order) the comparator
let idx = staff.binary_search_by(|e| e.id.cmp(&7));
assert_eq!(idx, Ok(1));

binary_search_by_key takes the target and a closure that projects the key. No .cmp(), nothing to get backwards:

1
2
3

let idx = staff.binary_search_by_key(&7, |e| e.id);
assert_eq!(idx, Ok(1));
assert_eq!(staff[idx.unwrap()].name, "Bo");

On a miss you get Err(i) — the index where the element would go to keep the slice sorted, so you can insert without a second search:

1
2
3
4

match staff.binary_search_by_key(&10, |e| e.id) {
    Ok(i)  => println!("found at {i}"),
    Err(i) => println!("would insert at {i}"), // Err(2)
}

One rule: the slice must already be sorted by the same key you project, otherwise the result is unspecified. When that holds, it’s O(log n) instead of the O(n) scan you’d write by hand.

Need the index of the last element that matches? The reflex is iter().rev().position(...) then len - 1 - i — and that arithmetic is a classic off-by-one. rposition searches from the back and hands you the real forward index.

The reversed-index trap

1
2
3
4
5
6
7

let bytes = [b'a', b'/', b'b', b'/', b'c'];

// "index of the last slash" — the fragile way
let from_end = bytes.iter().rev().position(|&b| b == b'/').unwrap();
let idx = bytes.len() - 1 - from_end;

assert_eq!(idx, 3);

position on a reversed iterator counts from the end, so you have to flip it back with len - 1 - i. Get the - 1 wrong and you’re off by one.

rposition does the flip for you

1
2
3
4
5

let bytes = [b'a', b'/', b'b', b'/', b'c'];

let idx = bytes.iter().rposition(|&b| b == b'/');

assert_eq!(idx, Some(3)); // real index, counted from the front

rposition walks from the back but returns the index in the original, forward order — no arithmetic, and None when nothing matches instead of a panic on the empty case.

It short-circuits from the right

Just as position stops at the first match from the front, rposition stops at the first match from the back — so it only scans the tail it needs:

1
2
3
4
5

let nums = [1, 2, 3, 4, 5, 6];

// last even number
let idx = nums.iter().rposition(|&n| n % 2 == 0);
assert_eq!(idx, Some(5)); // stopped immediately at 6

The requirement

rposition needs a DoubleEndedIterator (so it can walk backwards) that is also an ExactSizeIterator (so it knows the length to report the front index). Slices, Vec, and arrays give you both. A lazy adapter like filter isn’t ExactSizeIterator, so index a slice or collect first.

For string byte or substring searches, str::rfind is the more direct tool — but for an arbitrary predicate over any exact-size sequence, rposition is the one to reach for.

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.