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

Viewed 136110

For an array of size N, what is the number of comparisons required?

23 Answers
    int[] int_array = {4, 6, 2, 9, 1, 7, 4, 2, 9, 0, 3, 6, 1, 6, 8};
    int largst=int_array[0];
    int second=int_array[0];
    for (int i=0; i<int_array.length; i++){        
        if(int_array[i]>largst) { 
            second=largst;
            largst=int_array[i];
        }  
        else if(int_array[i]>second  &&  int_array[i]<largst) { 
            second=int_array[i];
        } 
    }

I suppose, follow the "optimal algorithm uses n+log n-2 comparisons" from above, the code that I came up with that doesn't use binary tree to store the value would be the following:

During each recursive call, the array size is cut in half.

So the number of comparison is:

1st iteration: n/2 comparisons

2nd iteration: n/4 comparisons

3rd iteration: n/8 comparisons

... Up to log n iterations?

Hence, total => n - 1 comparisons?

function findSecondLargestInArray(array) {
    let winner = [];
    if (array.length === 2) {
        if (array[0] < array[1]) {
            return array[0];
        } else {
            return array[1];
        }
    }
    for (let i = 1; i <= Math.floor(array.length / 2); i++) {
        if (array[2 * i - 1] > array[2 * i - 2]) {
            winner.push(array[2 * i - 1]);
        } else {
            winner.push(array[2 * i - 2]);
        }
    }
    return findSecondLargestInArray(winner);
}

Assuming array contain 2^n number of numbers.

If there are 6 numbers, then 3 numbers will move to the next level, which is not right.

Need like 8 numbers => 4 number => 2 number => 1 number => 2^n number of number

Related