# Finding numbers near the median in linear time

Problem:

Describe (English is enough) a linear algorithm that, given a set $$S$$ of $$n$$ distinct numbers and a positive integer $$k \leq n$$, returns the $$k$$ numbers in $$S$$ that are closest to the median of $$S$$.

I interpret the term linear algorithm to mean one that runs in $$O(n)$$ time. It is not clear to me if that means worst case or average case. I would tend to think worst case. \newline I claim that problem may not have a unique solution. For example, if we are given $$S = \{ 1, 2, 3, 4, 5 \}$$ and $$k = 2$$ then we have the following two valid solutions: \newline $$S = \{ 2, 3 \}$$ and $$S = \{ 3, 4 \}$$. Here is my algorithm, which I do not believe meets the performance requirements of the question:

Let ans be the set of numbers we want to return.
Compute the median of S and call that value m.

Initialize the set ans to the first k elements of S.
// One data structure to hold ans would be an array. A better choice might be
// a binary tree / heap.
for i = k+1 to n (inclusive)
if S[i] is closer to the median then the element of ans that is farthest
away from the median then
update ans by replacing that element with S[i]
end if
end for
return ans


I am assuming that we can find the median in $$O(n)$$ time. Depending on the data structure chosen for ans, the running time for the code will be $$O( n \log k )$$ which is linear in $$n$$. This does not seem right to me. Is it? If it is wrong, where did I go wrong?

Does this problem even have a valid solution?

• Your title asks to find the number near the mean, but your description asks to find the number near the median, which is different. The algorithm described by Yuval Filmus works for the median, but not the mean (but it can still works if you consider the array of $x_i - \overline{x}$ where $\overline{x}$ is the mean of the array). – Nathaniel Mar 9 at 19:05
• @Nathaniel Good Catch. I do mean median. The title was wrong. I fixed it. – Bob Mar 9 at 21:07

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.