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?

Answer 1

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.

Answer 2

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 V_t(n)).

Knuth gives an upper bound of n - t + (t-1)⌈lg(n + 2 - t)⌉ for V_t(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.