Selection and Closest Pair
Kent Quanrud · 77:58
Linear-time worst-case selection is possible without fully sorting: an exact median (or any pivot that discards a constant fraction) reduces general rank-\(k\) search to a smaller instance, and median-of-medians (grou...