Given 5 numbers, what is the minimum number of comparisons needed to find the median?
To quote Donald Knuth (via 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 Lower Bounds section).
Your goal is to find the k smallest values, where k is half the size of the list, rounded up (so k = 3; n = 5), and then take the largest of them. By typing this into the formula on the page, you get:
(5 - 3) + 1 + 1 + 2 = 6
In this case, the actual minimum number of comparisons required is also six.
If you doubt that finding the median is as difficult as finding the lowest values, you can refer to Knuth TAoCP Volume 3 Exercise # 2 after chapter 5.3.3.
source to share
There is a lot of material in Donald Knuth's Volume 3. See the art of computer programming in section 5.3.3 "Minimum Comparison Choice" for a more general question about the minimum number of comparisons required to select tth the largest of n values. (This value is denoted by V t (n)).
Knuth gives an upper estimate for n - t + (t-1) and lg (n + 2 - t) & rceil; for V t(n), achieved by defining the largest element n - t + 2 by the tournament system, removing that (since it cannot be tth largest) and replacing it with one of the remaining elements, continuing this procedure until all elements are part of of this procedure, and then the largest element in this step will be tth the largest from the original set. In this case n = 5 and t = 3, so the upper bound given by this formula is 6 comparison.
Knuth mentions that this upper bound is accurate when n & le; 6, so it applies in this case. In general, I understand that there are no general procedures for finding minimal comparison algorithms for selection (and sorting), and entries to increase the values of n usually use special tricks that either do not apply at all to larger values, or are just beaten with other tricks when n increases.
source to share