# Computing min and max using median of 3 elements

How can I write an O(n)-time algorithm to find the minimum and maximum, given a list of n elements drawn from a totally ordered set using the subroutine median3(x,y,z) which returns the index of three elements x,y,z? You are not allowed to read or compare the elements directly; the only operation that is allowed is invoke the median3 subroutine.

• If you'd like to make changes, please don't re-post your question in a new post. Instead, edit the existing question using the 'edit' link under the question.
– D.W.
Mar 1 '18 at 5:17
• Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
– Raphael
Mar 1 '18 at 9:09

## 1 Answer

Let the list be $x_1,\ldots,x_n$. The algorithm is as follows:

1. Let $S = \{x_1,x_2\}$.
2. For $i = 3,\ldots, n$:
• Add $x_i$ to $S$.
• Compute the median of $S$, and remove it from $S$.
3. Output $S$.

I'll let you figure out why this works.

Note that we cannot possibly tell which is the minimum and which is the maximum. Indeed, $\operatorname{median3}$ works the same for both the original order and its reverse.