selection algorithm problem

Question

Suppose you have an array A of n items, and you want to find the k items in A closest to the median of A. For example, if A contains the 9 values {7, 14, 10, 12, 2, 11, 29, 3, 4} and k = 5, then the answer would be the values {7, 14, 10, 12, 11}, since the median is 10 and these are the five values in A closest to the value 10. Give an algorithm to solve this problem in O(n) time.

I know that a selection algorithm (deep selection) is the appropriate algorithm for this problem, but I think that would run in O(n*logn) time instead of O(n). Any help would be greatly appreciated :)

Answer 1

You will first need to find the median, which can be done in O(n) (for example using Hoare's Quickselect algorithm).

Then you will need to implement a sorting algorithm which sorts the elements in the array according to their absolute distance to the median (smallest distances first).

If you were to sort the entire array this way, this would typically take somewhere from O(n * log n) to O(n^2), depending on the algorithm being used. However since you only need the first k values, the complexity can be reduced to O(k * log n) to O(k * n).

Since k is a constant and does not depend on the size of the array, the overall complexity in a worst case scenario will be: O(n) (for finding the median) + O(k * n) (sorting), which is O(n) overall.