I was wondering if this question belongs here or on StackOverflow, but it is a question of mathematical nature so this seems more appropriate.
We have an array $S$ of $n$ different numbers $S=a_1,a_2,a_3,...a_n$ where $i \neq j$ implies $a_i \neq a_j$. We know nothing about how the values in the array are arranged. All that we know is that it has $n$ numbers and they are all different. We can also assume that the median is an element in $S$.
We want to find the $k$ values that are closest to the median of the array, and we want to do it in $O(n)$.
Here is my idea that somehow simplifies the question but does not solve it entirely.
We have a method (we call it "Select" algorithm) that finds the median in $O(n)$. So finding the median is no problem and it's obviously something that needs to be done (but only once!), let's call the median $m$ for short.
Now define a new array $S' = a_1-m,a_2-m,a_3-m,...a_n-m$. That took another $n$ calculations so we are still at $O(n)$. Now go through all the elements of $S'$ and multiply by $-1$ the negative elements, another $n$ steps, still $O(n)$.
So now the problem is this: we have an array $S'$ with strictly non negative values. We want to find the $k$ smallest elements. How is this done in $O(n)$???
The naive approach would be to find the minimum ($n-1$ steps), remove it from the array, find the minimum again ($n-2$ steps) and so on, but that is $n-1+n-2+n-3+...+n-k-1$ but when $k$ approaches $n$, that approach will be $O(n^2)$ so that's no good.
Once you know $m$, in $O(n)$ time you can compute the array $B$ of values $|a_i - m|$ for each data element. Now you want the $k$ least of these, where $1 \le k \le n$. For some $s$, these will be the ones where $|a_i - m| \le s$. It would be easiest if $k$ was $n/2$: you could find $s$ by another application of your median algorithm. By the title "Select", I suspect that this algorithm does something more general than median-finding. But if median-finding is all you can do, you can accomplish it by adding in some "dummy" values that are either negative or greater than the maximum.