Medians & order statistics
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=\lfloor(n+1)/2\rfloor$ the (lower) median. Sorting then indexing costs $\Theta(n\lg n)$ — but the selection problem can be solved in $\Theta(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(\lg 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 $\Theta(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 $\Theta(n\lg n)$ harmonic-sum into a $\Theta(n)$ geometric sum. A partition is "helpful" (cuts the range to $\le 3n/4$) with probability $\ge \tfrac12$, so expected work is $\le 2n\sum_k (3/4)^k = 8n = O(n)$. Worst case is $\Theta(n^2)$ but, as in quicksort, only with negligible probability.
SELECT (median-of-medians) — worst-case $\Theta(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 $\lceil n/5\rceil$ medians; (5) partition around $x$ and recurse on the right side. $x$ guarantees at least $3n/10$ elements on each side are eliminated, so the recursive call has $\le 7n/10$ elements. The recurrence $T(n)\le T(n/5)+T(7n/10)+\Theta(n)$ solves to $\Theta(n)$ because $\tfrac15+\tfrac{7}{10}=\tfrac{9}{10}<1$.
Worked example
Binary search for $9$ in $\langle 1,3,4,7,9,11,15\rangle$ returns index $4$; searching for the absent $8$ returns $-1$. On $\langle 7,10,4,3,20,15\rangle$, 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.