0
$\begingroup$

We have an unordered sequence $A$ which consists of $n$ different numbers $A[1],A[2],A[3],\dots, A[n]$.

One member of $A$ is named an approximate median if $A$ contains at least $n/4$ members smaller than $x$ and at least $n/4$ members bigger than $x$.

How to design a deterministic algorithm than finds all approximate medians in time $O(n)$?

  • 0
    If the sequence is already ordered, then it's just a question of picking out the middle elements of the array. Otherwise, is an average-time solution acceptable? If so, (hint:) the standard solution is a variant of quicksort. $A$nd there are even (non-obvious) ways to optimize the pivot selection to give guaranteed linear run time.2011-11-07

2 Answers 2

4

There is a celebrated algorithm finding the (exact) median in linear time. By adding dummy elements, the algorithm can be used to find the $k$th largest element in linear time (in fact, the algorithm is already stated so that it finds the $k$th largest element for an arbitrary $k$). Find the $n/4$th largest element and $n/4$th smallest element in linear time. One pass through the array will then find all approximate medians.

  • 0
    That's your job. We don't solve the exercise for you, we help you solve it yourself.2011-11-08
0

If it is really ordered then it is trivial. Otherwise it is not trivial but you can still do it in O(n) using something like the implementation of nth_element().

  • 1
    @pressy: a naive selection algorithm to solve this problem is slower than linear; the linear nth_element algorithm is more like the celebrated exact median algorithm mentioned by yuval and may be thought of as its generalization.2011-11-07