Algorithms / Quickselect Kth

Least You Need to Know: Quickselect, kth Element, and One-Sided Recursion

Quickselect uses partitioning to find a target rank without fully sorting the array. Its main idea is that once the pivot rank is known, only one side can still contain the kth element. That one-sided recursion is why quickselect is typically faster than full quicksort when only a single rank is needed.

The least you need to know

Quickselect applies a partition step, then recurses only into the side that still contains the target rank.
If the pivot lands exactly at the target rank, the answer is found immediately.
Quickselect does not fully sort the array.
Randomized pivot choices give expected linear running time.
The algorithm's reasoning is rank-based: compare `k` to the pivot's final position.

Key notation

k target rank or target index after normalization

pivot index rank position determined by partition

one-sided recursion only one recursive subproblem remains relevant

Tiny worked example

Partition the array around a pivot.
Let `p` be the pivot's final rank.
If `p = k`, return the pivot.
If `k < p`, recurse left; if `k > p`, recurse right with the adjusted target rank.

Common mistakes

Students sometimes think quickselect sorts the side it discards, but that work is never needed.
The whole point is to avoid exploring both recursive sides.
Indexing conventions for `k` must be handled carefully.

How to recognize this kind of problem

The prompt asks for kth, median, percentile, or a single rank.
Partition logic is present but full ordering is unnecessary.
A key step is comparing the pivot position to the target rank.