# Design an $O(n)$ deterministic algorithm to find the approximate median of an array

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

-
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

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.