Hello!!!
I want to describe an algorithm with time complexity O(m) that, given a set M with m numbers and a positive integer p<= m, returns the p closest numbers to the median element of the set M.
low=m/2-(p-1)
high=(m-1)/2+(p-1)
Algorithm(A,begin,end,low,high){
if (begin<end){
k=medianofMedians(A,low,high)
q=hoare(A,start,begin,end,k)
if (q>low) Algorithm(A,begin,q-1,low,high)
if (q<high) Algorithm(A,q+1,end,low,high)
}
}
Is it right? How could we find and return the p closest numbers to the median element?