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.

  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Mar 1 '18 at 5:17
  • $\begingroup$ 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! $\endgroup$
    – Raphael
    Mar 1 '18 at 9:09

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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