Algorithms

#075 Apr 2026

75. select_nth_unstable — Find the Kth Element Without Sorting

You’re sorting an entire Vec just to grab the median or the top 3 elements. select_nth_unstable does it in O(n) — no full sort required.

The classic approach: sort everything, then index:

1
2
3
4
let mut scores = vec![82, 45, 99, 67, 73, 91, 55];
scores.sort();
let median = scores[scores.len() / 2];
assert_eq!(median, 73);

That’s O(n log n) to answer an O(n) question. select_nth_unstable uses a partial-sort algorithm (quickselect) to put the element at a given index into its final sorted position — everything before it is smaller or equal, everything after is greater or equal:

1
2
3
4
let mut scores = vec![82, 45, 99, 67, 73, 91, 55];
let mid = scores.len() / 2;
scores.select_nth_unstable(mid);
assert_eq!(scores[mid], 73);

The method returns three mutable slices — elements below, the pivot element, and elements above — so you can work with each partition directly:

1
2
3
4
5
6
7
let mut data = vec![10, 80, 30, 90, 50, 70, 20];
let (lower, median, upper) = data.select_nth_unstable(3);
// lower contains 3 elements all <= *median
// upper contains 3 elements all >= *median
assert_eq!(*median, 50);
assert!(lower.iter().all(|&x| x <= 50));
assert!(upper.iter().all(|&x| x >= 50));

Need the top 3 scores without sorting the full list? Select the boundary, then sort only the small tail:

1
2
3
4
5
6
let mut scores = vec![82, 45, 99, 67, 73, 91, 55];
let k = scores.len() - 3;
scores.select_nth_unstable(k);
let top_3 = &mut scores[k..];
top_3.sort_unstable(); // sort only 3 elements, not all 7
assert_eq!(top_3, &[82, 91, 99]);

Custom ordering works too. Find the median by absolute value:

1
2
3
4
let mut vals = vec![-20, 5, -10, 15, -3, 8, 1];
let mid = vals.len() / 2;
vals.select_nth_unstable_by_key(mid, |v| v.abs());
assert_eq!(vals[mid].abs(), 8);

The “unstable” in the name means equal elements might be reordered (like sort_unstable) — it doesn’t mean the API is experimental. This is stable since Rust 1.49, available on any [T] where T: Ord.

#073 Apr 2026

numerics overflow algorithms

73. u64::midpoint — Average Two Numbers Without Overflow

Computing the average of two integers sounds trivial — until it overflows. The midpoint method gives you a correct result every time, no wider types required.

The classic binary search bug lurks in this innocent-looking line:

1
let mid = (low + high) / 2;

When low and high are both large, the addition wraps around and you get garbage. This has bitten production code in every language for decades.

The textbook workaround avoids the addition entirely:

1
let mid = low + (high - low) / 2;

This works — but only when low <= high, and it’s one more thing to get wrong under pressure.

Rust’s midpoint method handles all of this for you:

1
2
3
4
5
6
7
8
9
let a: u64 = u64::MAX - 1;
let b: u64 = u64::MAX;

// This would panic in debug or wrap in release:
// let avg = (a + b) / 2;

// Safe and correct:
let avg = a.midpoint(b);
assert_eq!(avg, u64::MAX - 1);

It works on signed integers too, rounding toward zero:

1
2
3
let x: i32 = -3;
let y: i32 = 4;
assert_eq!(x.midpoint(y), 0);  // rounds toward zero, not -∞

And on floats, where it’s computed without intermediate overflow:

1
2
3
let a: f64 = f64::MAX;
let b: f64 = f64::MAX;
assert_eq!(a.midpoint(b), f64::MAX);  // not infinity

Here’s a binary search that actually works for the full u64 range:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
fn binary_search(sorted: &[i32], target: i32) -> Option<usize> {
    let mut low: usize = 0;
    let mut high: usize = sorted.len();
    while low < high {
        let mid = low.midpoint(high);
        match sorted[mid].cmp(&target) {
            std::cmp::Ordering::Less => low = mid + 1,
            std::cmp::Ordering::Greater => high = mid,
            std::cmp::Ordering::Equal => return Some(mid),
        }
    }
    None
}

let data = vec![1, 3, 5, 7, 9, 11];
assert_eq!(binary_search(&data, 7), Some(3));
assert_eq!(binary_search(&data, 4), None);

Available on all integer types (u8 through u128, i8 through i128, usize, isize) and floats (f32, f64). No crate needed — it’s in the standard library.