MHB Finding the $p$ Closest Elements to Median of Set $M$ in $O(m)$ Time

[evinda]

Hello! (Wave)
I want to describe an algorithm with time complexity $O(m)$ that, given a set $M$ with $m$ numbers and a positive integer $p \leq m$, returns the $p$ closest numbers to the median element of the set $M$.

How could we do this? (Thinking)

 

[evinda]

What could we do in order to find the $p$ closest numbers to the median element of the set $M$ ? Could you give me a hint? (Thinking)

 

[PvsNP]

Hello! (Wave)
I want to describe an algorithm with time complexity $O(m)$ that, given a set $M$ with $m$ numbers and a positive integer $p \leq m$, returns the $p$ closest numbers to the median element of the set $M$.

How could we do this? (Thinking)

Complexity $O(m)$ algorithm operating on a list of size $m$ implies that you're only allowed to do a single pass of the list. Is this list of numbers pre-sorted or not?

 

[evinda]

Complexity $O(m)$ algorithm operating on a list of size $m$ implies that you're only allowed to do a single pass of the list. Is this list of numbers pre-sorted or not?

No, I think that the algorithm should work for each case... (Thinking)

 

[PvsNP]

No, I think that the algorithm should work for each case... (Thinking)

Without thinking about it in depth, I'm not sure that this is possible. Median is the "middle" value on a set of ranked values, and no sorting algorithm runs in $O(n)$ time.

EDIT: I'm wrong. It's possible to find the median in $O(n)$ time. See if this helps you: Median of medians - Wikipedia, the free encyclopedia

 

[evinda]

Doing it like that:

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)
   }
}

we will have the interval to which the $p$ elements we are looking for belong.
But this interval will contain $2p$ elements.
How can we find the $p$ nearest elements to the median? (Sweating)