Finding elements near median

Q : Given an unsorted array A of n distinct numbers and an integer k where
1 <= k <= n, design an algorithm that finds the k numbers in A that
are closest in value to the median of A in O(n) time.


Sol :

1. Find the median, M: O(n)
2. Form a second array containing y(i) = abs(x(i) - M): O(n)
3. Find the kth smallest element of this array, K: O(n)
4. Scan the original array and locate the first k elements such that
abs(x(i) - M) <= K: O(n)

Total algorithm: O(n).