[Solved]: prove that minimal number of comparisons to find median among five elements is 5

Problem Detail: 

I would like to prove that we need at least five comparisons to find median amoung five numbers.

And my proposition: Let's consider tree of comparisons. There are at least $5 \cdot {4\choose 2} = 30$ possiblities, so in our tree we have at least $30$ leaves. So what is minimal height of this tree when we have at least $30$ leaves. (height is number of comparisons).
So $$height \ge \log_2(30) > 4$$ Hence, $height \ge 5$.

Is it correct proof ?

Asked By : M.Swe

Answered By : atulgangwar

Your proof is correct. But I don't think 5 comparisons is achievable. Here is the algorithm that finds the median in 6 comparisons.

1. Sort the first two pairs. [ 2 comparisons]

2. Order the pairs w.r.t. their respective larger element. [ 1 comparison]

   Call the result $[a,b,c,d,e]$; we know $a<b<d$ and $c<d$. Now there are 3 elements less than $d$, hence $d$ can't be the median( i.e. $3^{rd}$element of the sorted array)

3. WLOG say $c<e$ and $a<b$ (known already). Order the pairs w.r.t. their respective larger element. WLOG $a<b<e$ and $c<e$. Compare $c$ & $b$, greater one is the median. [ 3 comparisons - 1 for $c$ & $e$, 1 for ordering the pairs and 1 for $b$ & $c$ ]

Hence, total number of comparisons is equal to 6.

Idea taken from here .

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/45374