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