Medians & order statistics

◈ 5 cards

Binary search as a warm-up; RANDOMIZED-SELECT expected Θ(n) via one-sided recursion; median-of-medians SELECT worst-case Θ(n) with groups of 5.

Finding the $i$ -th smallest without sorting

The $i$ -th order statistic is the $i$ -th smallest element; $i = 1$ is the minimum, $i = n$ the maximum, $i = ⌊(n + 1) /2 ⌋$ the (lower) median. Sorting then indexing costs $Θ (n l g n)$ — but the selection problem can be solved in $Θ (n)$ . You don't need the whole order, only which side of a pivot the answer lies on.

Warm-up: binary search

On a sorted array, binary search finds a target in $O (l g n)$ by halving the live range each step — "one-sided linear search." It's the prototype for the idea behind selection: identify which half contains the answer and discard the other.

RANDOMIZED-SELECT — expected $Θ (n)$

This is one-sided quicksort. Call RANDOMIZED-PARTITION to get a random pivot at rank $r$ within the current range. If $i = r$ , return the pivot. If $i < r$ , recurse only on the low side; if $i > r$ , recurse only on the high side (adjusting $i$ ). Recursing on one side is the whole difference from quicksort: it turns a $Θ (n l g n)$ harmonic-sum into a $Θ (n)$ geometric sum. A partition is "helpful" (cuts the range to $\leq 3 n /4$ ) with probability $\geq \frac{1}{2}$ , so expected work is $\leq 2 n \sum_{k} (3/4)^{k} = 8 n = O (n)$ . Worst case is $Θ (n^{2})$ but, as in quicksort, only with negligible probability.

SELECT (median-of-medians) — worst-case $Θ (n)$

To kill even the unlikely worst case, choose a provably good pivot. (1) Split into groups of 5; (2) insertion-sort each group; (3) take each group's median; (4) recursively SELECT the median $x$ of those $⌈ n /5 ⌉$ medians; (5) partition around $x$ and recurse on the right side. $x$ guarantees at least $3 n /10$ elements on each side are eliminated, so the recursive call has $\leq 7 n /10$ elements. The recurrence $T (n) \leq T (n /5) + T (7 n /10) + Θ (n)$ solves to $Θ (n)$ because $\frac{1}{5} + \frac{7}{10} = \frac{9}{10} < 1$ .

Worked example

Binary search for $9$ in $⟨ 1, 3, 4, 7, 9, 11, 15 ⟩$ returns index $4$ ; searching for the absent $8$ returns $- 1$ . On $⟨ 7, 10, 4, 3, 20, 15 ⟩$ , RANDOMIZED-SELECT returns the $3$ rd smallest $= 7$ , the $1$ st $= 3$ , and the $6$ th $= 20$ . The runnable exercise implements both and reproduces these.

One-sided recursion. Each partition places one element and throws away a whole side, so the work is a shrinking geometric series rather than quicksort’s harmonic one.

Step 1 of SELECT: groups of 5, each insertion-sorted so its median sits in the centre column. The pivot x = 9 is the median of those three medians, which is what forces at least 3n/10 elements out on each side.