What is the most efficient algorithm for finding the median of an array when the available operations are limited to Max(), Min(), Multiply, Add, and no conditionals are allowed. Pivots and sorts are not allowed. The algorithm I have come up with so far seems very inefficient and goes like so:
- For an array of length n, create a working array of length 2n by doing pairwise Max() comparisons for every pair of elements in the input array. This 2n array is guaranteed not to contain the lowest value from the original (or one fewer of the lowest value if there were ties for the lowest value)
- Recursively call (1) n/2 times
- Take min() of final array
There's got to be a faster algorithm!