C++ program to find the second largest element in an array

The purpose of an array is to store similar types of data in a series of memory locations that can be accessed using base addresses and indexes. We use arrays in many different applications to hold data for various purposes. Finding the smallest and largest elements is a fairly common example of arrays, which are needed in several applications including sorting, etc. In this article, we will learn how to find the second largest element from an array in C.

Understand concepts through examples

Given array A = [89, 12, 32, 74, 14, 69, 45, 12, 99, 85, 63, 32]
The second largest element is 89

In the above example, there are 12 elements in the array. The largest element in the array is 99, and the second largest element is 89. In the first method, to find the second largest element, we only need to sort the elements in ascending or descending order, and then directly return the second to last or second element to obtain the second largest element. The algorithm is as follows -

algorithm

• Get an array A

of size n

• Sort array A according to the non-increasing order of the values ​​​​of array A

• Return A[ 1 ] // Because the 0th index contains the largest element

Example

#include <iostream>
#include <algorithm>
# define Z 30

using namespace std;

void displayArr(int arr[], int n ) {
   for( int i = 0; i < n; i++ ){
      cout << arr[ i ] << ", ";
   } 
   cout << endl;
} 

int getSecondLargest( int A[], int n ){
   sort( A, A + n, greater<int>() );
   return A[ 1 ];
}

int main() {
   int arr[ Z ] = {84, 56, 21, 32, 74, 96, 85, 41, 21, 94, 20, 37, 36, 75, 20};
   int n = 15;
   
   cout << "Given array elements: ";
   displayArr( arr, n);
   
   cout << "The second largest element: " << getSecondLargest( arr, n ); 
}

Output

Given array elements: 84, 56, 21, 32, 74, 96, 85, 41, 21, 94, 20, 37, 36, 75, 20, 
The second largest element: 94

Use double traversal

The above method seems simple, but this process is not efficient for this problem. Since we are using sorting, performing the sorting takes at least O(n.log n) time. But we can also solve this problem in linear time. In the current method, we iterate through the array of elements twice and find the second largest element. Let's check the algorithm.

algorithm

• Get an array A

of size n

• Maximum := -infinity

• Maximum seconds := -infinity

• For each element e in A, execute

  • If e is greater than Maximum, then

    • Max=e

  • End if

• Finish

• For each element e in A, execute

  • If e is greater than secLargest but less than maximum, then

    • Second maximum = e

  • End if

• Finish

• Return the maximum number of seconds

Example

#include <iostream>
#include <algorithm>
# define Z 30

using namespace std;

void displayArr(int arr[], int n ) {
   for( int i = 0; i < n; i++ ){
      cout << arr[ i ] << ", ";
   } 
   cout << endl;
} 

int getSecondLargest( int A[], int n ){
   int largest = -99999;
   for( int i = 0; i < n; i++ ) {
      if( A[i] > largest ){
         largest = A [ i ]; 
      }   
   }
   int secLargest = -99999;
   for( int i = 0; i < n; i++ ) {
      if( A[i] > secLargest && A[i] < largest ){
         secLargest = A [ i ]; 
      }   
   }
   return secLargest;
}

int main() {
   int arr[ Z ] = {84, 56, 21, 32, 74, 96, 85, 41, 21, 94, 20, 37, 36, 75, 20};
   int n = 15;
   
   cout << "Given array elements: ";
   displayArr( arr, n);
   
   cout << "The second largest element: " << getSecondLargest( arr, n ); 
}

Output

Given array elements: 84, 56, 21, 32, 74, 96, 85, 41, 21, 94, 20, 37, 36, 75, 20, 
The second largest element: 94

Use single traversal

The above solution iterates through the array twice. In the first run, find the largest element from the array, then in the second run, search for the largest element that is not larger than the first largest. Since the array is a linear data structure, each traversal takes O(n) time, so the final solution time is O(2n), which is also linear, similar to O(n). But this is not an efficient solution, we can only solve this problem with one pass. Let's see its algorithm.

algorithm

• Get an array A

of size n

• Maximum := A[0]

• For starting index from 1 to n - 1, execute

  • If the current element A[i] is greater than maximum, then

    • Second maximum := maximum

    • Maximum := A[ i ]

  • Otherwise when A[ i ] is between largest and secLargest, then

    • Maximum seconds := A[ i ]

  • End if

• Finish

• Return the maximum number of seconds

Example

#include <iostream>
#include <algorithm>
# define Z 30

using namespace std;

void displayArr(int arr[], int n ) {
   for( int i = 0; i < n; i++ ){
      cout << arr[ i ] << ", ";
   } 
   cout << endl;
} 

int getSecondLargest( int A[], int n ){
   int largest = A[ 0 ];
   int secLargest = -9999;
   for( int i = 1; i < n; i++ ) {
      if( A[i] > largest ){
         secLargest = largest; 
         largest = A[ i ];
      }   
      else if( secLargest < A[ i ] && A[ i ] != largest ) {
         secLargest = A[ i ];
      }
   } 
   return secLargest;
}

int main() {
   int arr[ Z ] = {84, 56, 21, 32, 74, 96, 85, 41, 21, 94, 20, 37, 36, 75, 20};
   int n = 15;
   
   cout << "Given array elements: ";
   displayArr( arr, n);
   
   cout << "The second largest element: " << getSecondLargest( arr, n ); 
}

Output

Given array elements: 84, 56, 21, 32, 74, 96, 85, 41, 21, 94, 20, 37, 36, 75, 20, 
The second largest element: 94

in conclusion

In this article, we learned about three different ways to find the second largest element from a given array. The first method is to use sorting. However, this solution is not efficient and takes at least O(n log n ) time. The latter solutions are very efficient since they require linear time. The second solution is to use a double pass over the array, which can also be optimized with a single pass as shown in the third solution.

The above is the detailed content of C++ program to find the second largest element in an array. For more information, please follow other related articles on the PHP Chinese website!