Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$?

share|improve this question
He didn't say they are ordered, just that they are different. –  GEdgar Nov 7 '11 at 18:46
@GEdgar thank you I think I misunderstood the term "ordered sequence". –  Listing Nov 7 '11 at 18:51
So, the OP should clarify, because what he means is not clear. –  GEdgar Nov 7 '11 at 18:55
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. And there are even (non-obvious) ways to optimize the pivot selection to give guaranteed linear run time. –  Henning Makholm Nov 7 '11 at 19:01
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
Can you add pseudocode for that? –  pressy_paris Nov 8 '11 at 18:59
That's your job. We don't solve the exercise for you, we help you solve it yourself. –  Yuval Filmus Nov 8 '11 at 19:54
add comment

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().

share|improve this answer
I was thinking using selection algorithm in this. Can you explain a bit more? –  pressy_paris Nov 7 '11 at 19:06
@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. –  opt Nov 7 '11 at 19:32
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.