Finding numbers near the median in linear time
There is an algorithm that finds the $\ell$-th smallest element in an array of length $n$ in time $O(n)$. You can find the $(n-k)/2$-th smallest and the $(n+k)/2$-th smallest elements in $O(n)$ using this algorithm, and then, using an additional pass, find all elements in between.