242. slice::binary_search_by_key — Find a Record by One Field, No Hand-Written Comparator

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.