Finding largest and second-largest out of N numbers

Question

Given n numbers, how do I find the largest and second largest number using at most n+log(n) comparisons?

Note that it's not O(n+log(n)), but really n+log(n) comparisons.

Answer 1

pajton gave a comment.

Let me elaborate.

As pajton said, this can be done by tournament selection.

Think of this as a knock out singles tennis tournament, where player abilities have a strict order and the outcome of a match is decided solely by that order.

In the first round half the people are eliminated. In the next round another half etc (with some byes possible).

Ultimately the winner is decided in the last and final round.

This can be viewed as a tree.

Each node of the tree will be the winner of the match between the children of that node.

The leaves are the players. The winner of the first round are the parents of the leaves etc.

This is a complete binary tree on n nodes.

Now follow the path of the winner. There are log n matches the winner has played. Now consider the losers of those log n matches. The second best must be the best among those.

The winner is decided in n-1 matches (you knock out one per match) and the winner among the logn is decided in logn -1 matches.

Thus you can decide the largest and second largest in n+logn - 2 compares.

In fact, it can proven that this is optimal. In any comparison scheme in the worst case, the winner would have to play logn matches.

To prove that assume a point system where after a match the winner gets the points of the loser. Initially all start out with 1 point each.

At the end the final winner has n points.

Now given any algorithm, it could be arranged so that player with more points is always the winner. Since the points of any person at most double in any match in that scenario, you require at least log n matches played by the winner in the worst case.

Answer 2

Is there a problem with this? It's at most 3n comparisons (not counting the i < n comparison). If you count that, it's 4n (or 5n in the second example).

double first = -1e300, second = -1e300;
for (i = 0; i < n; i++){
  if (a[i] > first){
    second = first;
    first = a[i];
  }
  else if (a[i] > second && a[i] < first){
    second = a[i];
  }
}

another way to code it:

for (i = 0; i < n; i++) if (a[i] > first) first = a[i];
for (i = 0; i < n; i++) if (a[i] < first && a[i] > second) second = a[i];