find out the largest and second largest number in an array

Question: Write an efficient C program to find smallest and second smallest element in an array.

Solution
Method 1 - Compare each element with current max and second max

Algorithm

1) Initialize both first and second smallest as a[0]
   first = second = a[0]
2) Loop through all the elements.
   a) If the current element is greater than firstMax, then update firstMax 
       and secondMax. 
   b) Else if the current element is greater than second then update 
    secondMax

pseudocode

largest = numbers[0];
secondLargest = null
for (i=1 to numbers.length-1) {    
    if numbers[i] > largest {
        secondLargest = largest;
        largest = numbers[i];
    else
        if numbers[i] > secondLargest {
            secondLargest = numbers[i];
        }
    }
}

Time Complexity: O(n)
 Number of comparisons atmost will be 2(N-1)

Method 2 - Tournament principle

The optimal algorithm uses n+log n-2 comparisons. Think of elements as competitors, and a tournament is going to rank them.
First, compare the elements, as in the tree

   |
  / \
 |   |
/ \ / \
x x x x

this takes n-1 comparisons and each element is involved in comparison at most log n times. You will find the largest element as the winner.
The second largest element must have lost a match to the winner (he can't lose a match to a different element), so he's one of the log n elements the winner has played against. You can find which of them using log n - 1 comparisons.

Example-

1. Start with comparing elements of the n element array in odd and even positions and determining largest element of each pair. This step requires n/2 comparisons. Now you've got only n/2 elements. Continue pairwise comparisons to get n/4, n/8, ... elements. Stop when the largest element is found. This step requires a total of n/2 + n/4 + n/8 + ... + 1 = n-1 comparisons.
2. During previous step, the largest element was immediately compared with log₂(n) other elements. You can determine the largest of these elements in log₂(n)-1 comparisons. That would be the second-largest number in the array.

 So, looking at the tree above, 9 is the winner, but we find 2nd winner on level 2 and so on.

From the above picture we can see that we have found the max in the array. Now we know 9 is MAX but we can't say 7 is SECOND MAX since that would be wrong. Number of Comparison's to find MAX = (n/2) + logn(n) = (n-1) in the above case so the above algo is also optimal for finding MAX ; since conventional algo also takes the same. To find SECOND MAX take the players that were directly defeated by MAX. i.e. 9 DIRECTLY DEFEATED BY MAX = 8, 3, 7 If we play the above tournament among 8, 3, 7 we get 8 as second MAX we for this tournament we needed just 2 comparison's Total comparisons to find MAX and second MAX using tournament principle = (n/2) + log(n) + log(n) = (n-1) + log(n) Now to find kth MAX we can play (k/2) such tournaments since in one tournament we get MAX and second MAX..then exclude them and play the tournament again(k/2) times So total comparisons to find kth MAX using above method = (k/2) ((n-1) + log(n)) However in the conventional algo it would be (k/2 passes of array)(2n comparisons to find MAX and second MAX) = k * n So tournament algo is more optimal eg:: if k = 4 and n = 8 Comparison's by conventional algo = 4 * 8 = 32 Comparison's by Tournament algo = (4/2) ((7) + 3) = 2 * 10 = 20  

Here is the code for tournament principle:

Here is the solution taken from stackoverflow:
To make things work, there are two assumptions:
1) number of elements in the array is the power of 2
2) there are no duplicates in the array
The whole process consists of two steps:
1. building a 2D array by comparing two by two elements. First row in the 2D array is gonna be the entire input array. Next row contains results of the comparisons of the previous row. We continue comparisons on the newly built array and keep building the 2D array until an array of only one element (the largest one) is reached.
2. we have a 2D-array where last row contains only one element: the largest one. We continue going from the bottom to the top, in each array finding the element that was "beaten" by the largest and comparing it to the current "second largest" value. To find the element beaten by the largest, and to avoid O(n) comparisons, we must store the index of the largest element in the previous row. That way we can easily check the adjacent elements. At any level (above root level),the adjacent elements are obtained as:

leftAdjacent = rootIndex*2
rightAdjacent = rootIndex*2+1,

where rootIndex is index of the largest(root) element at the previous level.

public static Integer findSecondLargest(List<Integer> list) {
        if (list == null) {
            return null;
        }
        if (list.size() == 1) {
            return list.get(0);
        }
        List<List<Integer>> structure = buildUpStructure(list);
        System.out.println(structure);
        return secondLargest(structure);

    }

    public static List<List<Integer>> buildUpStructure(List<Integer> list) {
        List<List<Integer>> newList = new ArrayList<List<Integer>>();
        List<Integer> tmpList = new ArrayList<Integer>(list);
        newList.add(tmpList);
        int n = list.size();
        while (n>1) {
            tmpList = new ArrayList<Integer>();
            for (int i = 0; i<n; i=i+2) {
                Integer i1 = list.get(i);
                Integer i2 = list.get(i+1);
                tmpList.add(Math.max(i1, i2));
            }
            n/= 2;
            newList.add(tmpList);   
            list = tmpList;
        }
        return newList;
    }

    public static Integer secondLargest(List<List<Integer>> structure) {
        int n = structure.size();
        int rootIndex = 0;
        Integer largest = structure.get(n-1).get(rootIndex);
        List<Integer> tmpList = structure.get(n-2);
        Integer secondLargest = Integer.MIN_VALUE;
        Integer leftAdjacent = -1;
        Integer rightAdjacent = -1;
        for (int i = n-2; i>=0; i--) {
            rootIndex*=2;
            tmpList = structure.get(i);
            leftAdjacent = tmpList.get(rootIndex);
            rightAdjacent = tmpList.get(rootIndex+1); 
            if (leftAdjacent.equals(largest)) {
                if (rightAdjacent > secondLargest) {
                    secondLargest = rightAdjacent;
                }
            }
            if (rightAdjacent.equals(largest)) {
                if (leftAdjacent > secondLargest) {
                    secondLargest = leftAdjacent;
                }
                rootIndex=rootIndex+1;
            }
        }

        return secondLargest;
    }

Reference - stackoverflow