Describe an $\O(n)$-time algorithm that, given a set $S$ of $n$ distinct
numbers and a positive integer $k \le n$, determines the $k$ numbers in $S$
that are closest to the median of $S$.
This is a fun exercise.
We find the median of the array in linear time
We find the distance of each other element to the median in linear time
We find the $k$-th order statistic of the distance, again, in linear time
We select only the elements that have distance lower than or equal to the
$k$-th order statistic