Find the second largest element in an array with the minimum number of comparisons

I meet this question in an interview. It is actually a famous problem, whose solution is available here .

Here my thinking is provided.

1, The simplest case, suppose there are four elements, a,b,c,d, the minimum number of comparisons is 4:

a < b, c < d    ->   b < d  -> max(b,c) is the second largest element.

That is, we compare (a,b), (c,d) to get the largest values b,d, then find the largest value d, the second largest value is in the set of all elements that have been compared with d, that is, b or c.


2, Suppose we have 2n elements: (a,b), (c,d), (e,f), ....... We have n pairs, so select the larger element in each pair to form an n-array: b,d,f....In total n comparison is needed.

Suppose our algorithm can find the largest two values from b,d,f,...., which is (b,d) with b < d, for example.

The second largest element can either be b or c, compare b vs c we get the second largest element.

Thus, if x(2n) is the number of comparisons needed for an 2n-array, we have x(2n) = n + x(n) + 1

Solve this recursive function with x(4) = 4, we get x(n) = n + log2(n) - 2.