Find Second largest number in array at most n+log₂(n)−2 comparisons

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.

---

Example: array of 8 numbers [10,9,5,4,11,100,120,110].

Comparisons on level 1: [10,9] ->10 [5,4]-> 5, [11,100]->100 , [120,110]-->120.

Comparisons on level 2: [10,5] ->10 [100,120]->120.

Comparisons on level 3: [10,120]->120.

Maximum is 120. It was immediately compared with: 10 (on level 3), 100 (on level 2), 110 (on level 1).

Step 2 should find the maximum of 10, 100, and 110. Which is 110. That's the second largest element.

sly s's answer is derived from this paper, but he didn't explain the algorithm, which means someone stumbling across this question has to read the whole paper, and his code isn't very sleek as well. I'll give the crux of the algorithm from the aforementioned paper, complete with complexity analysis, and also provide a Scala implementation, just because that's the language I chose while working on these problems.

Basically, we do two passes:

1. Find the max, and keep track of which elements the max was compared to.
2. Find the max among the elements the max was compared to; the result is the second largest element.

In the picture above, 12 is the largest number in the array, and was compared to 3, 1, 11, and 10 in the first pass. In the second pass, we find the largest among {3, 1, 11, 10}, which is 11, which is the second largest number in the original array.

Time Complexity:

• All elements must be looked at, therefore, n - 1 comparisons for pass 1.
• Since we divide the problem into two halves each time, there are at most log₂n recursive calls, for each of which, the comparisons sequence grows by at most one; the size of the comparisons sequence is thus at most log₂n, therefore, log₂n - 1 comparisons for pass 2.

• Total number of comparisons <= (n - 1) + (log₂n - 1) = n + log₂n - 2

  def secondLargest(xs: IndexedSeq[Int]): Int = {
      def max(lo: Int, hi: Int, ys: IndexedSeq[Int]): (Int, IndexedSeq[Int]) = {
        if (lo >= hi) {
          (ys(lo), IndexedSeq.empty[Int])
        } else {
          val mid = lo + (hi - lo) / 2
          val (x, a) = max(lo, mid, ys)
          val (y, b) = max(mid + 1, hi, ys)
  
          if (x > y) {
            (x, a :+ y)
          } else {
            (y, b :+ x)
          }
        }
      }
  
      val (_, comparisons) = max(0, xs.size - 1, xs)
      max(0, comparisons.size - 1, comparisons)._1
  }
  

I have implemented this algorithm in Java answered by @Evgeny Kluev. The total comparisons are n+log2(n)−2. There is also a good reference: http://users.csc.calpoly.edu/~dekhtyar/349-Spring2010/lectures/lec03.349.pdf. This is similar to the top voted algorithm. Hope my solution is helpful. Thanks.

public class op1 {

private static int findSecondRecursive(int n, int[] A){
    int[] firstCompared = findMaxTournament(0, n-1, A); //n-1 comparisons;
    int[] secondCompared = findMaxTournament(2, firstCompared[0]-1, firstCompared); //log2(n)-1 comparisons.
    //Total comparisons: n+log2(n)-2;
    return secondCompared[1];
}

private static int[] findMaxTournament(int low, int high, int[] A){
    if(low == high){
        int[] compared = new int[2];
        compared[0] = 2;
        compared[1] = A[low];
        return compared;
    }
    int[] compared1 = findMaxTournament(low, (low+high)/2, A);
    int[] compared2 = findMaxTournament((low+high)/2+1, high, A);
    if(compared1[1] > compared2[1]){
        int k = compared1[0] + 1;
        int[] newcompared1 = new int[k];
        System.arraycopy(compared1, 0, newcompared1, 0, compared1[0]);
        newcompared1[0] = k;
        newcompared1[k-1] = compared2[1];
        return newcompared1;
    }
    int k = compared2[0] + 1;
    int[] newcompared2 = new int[k];
    System.arraycopy(compared2, 0, newcompared2, 0, compared2[0]);
    newcompared2[0] = k;
    newcompared2[k-1] = compared1[1];
    return newcompared2;
}

private static void printarray(int[] a){
    for(int i:a){
        System.out.print(i + " ");
    }
    System.out.println();
}

public static void main(String[] args) {
    //Demo.
    System.out.println("Origial array: ");
    int[] A = {10,4,5,8,7,2,12,3,1,6,9,11};
    printarray(A);
    int secondMax = findSecondRecursive(A.length,A);
    Arrays.sort(A);
    System.out.println("Sorted array(for check use): ");
    printarray(A);
    System.out.println("Second largest number in A: " + secondMax);
}

}