What is the most efficient algorithm for finding the median of an array when the

Question

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!

Explanation / Answer

I can get you an improvement for the first step; every time you do that first step, you're basically trying to find the minimum, and then continue on the rest of the array. You don't need to do all that just to find the minimum; instead of making that large array (which sounds like it contains (n2) elements, not 2n, unless I misunderstood you), you can basically do the following:

Starting from the left, take every pair of consecutive elements, and put the minimum of the two on the right. Something like this in pseudocode:

temp1 = min(array[i], array[i+1])
temp2 = max(array[i], array[i+1])

array[i] = temp2
array[i+1] = temp1

What will happen is that the minimum element gets moved all the way to the far right using 2(n?1) mins and maxs. We can then do our recursive call on the first n?1 elements, and repeat until we finally pull out the median.1

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.