given 5 numbers, what is the minimum number of comparisons needed to find the median?
Question
how do you setup minimum number of comparisons in general?
Solution
To cite Donald Knuth (by way of Wikipedia, since I don't have my copy of TAOCP at the moment), the lower bound for the number of comparisons is six:
http://en.wikipedia.org/wiki/Selection_algorithm (scroll down to the section entitled "Lower Bounds").
Your goal is, effectively, to find the k lowest values where k is half the size of the list, rounded up, (so, k = 3; n = 5) and then take the max of those. Plugging that into the formula there on the page, you get:
(5 - 3) + 1 + 1 + 2 = 6
In this case, the actual minimum number of required comparisons is also six.
If you're in doubt that the task of finding the median is as hard as finding k lowest values, you may refer to Knuth's TAoCP, volume 3, excercise #2 after 5.3.3 chapter.
OTHER TIPS
There is a lot of material on this in volume 3 of Donald Knuth's The Art of Computer Programming, in section 5.3.3, Minimum-Comparison Selection, where the more general question of the minimum number of comparisons required to select the tth largest of n values is considered. (This value is denoted by Vt(n)).
Knuth gives an upper bound of n - t + (t-1)⌈lg(n + 2 - t)⌉ for Vt(n), achieved by first determining the largest element of n - t + 2 by a tournament system, removing this (since it cannot be the tth largest) and replacing it with one of the remaining elements, continuing this procedure until all elements have been a part of this procedure, and then the largest element at this stage is the tth largest of the original set. In this case, n = 5 and t = 3, so the upper bound given by this formula is 6 comparisons.
Knuth mentions that this upper bound is exact when n ≤ 6, so that applies in this case. In general, my understanding is that there are no general procedures for finding minimum-comparison algorithms for selection (and sorting), and records for increasing values of n typically use special tricks that either are not generally applicable to larger values or are simply beaten by other tricks when n increases.