Program to find the largest element in an array

Largest element in an array (Sorted)

Since the array is already sorted in either order, we can get the largest element at the first or last position depending upon the sorting order of the array.

If we are not provided with the sorted order, we can always compare the first and last elements to decide the sorted array's order.

1. If the first element is greater than the last, the array is sorted in non-increasing order.
2. If the first element is smaller than the last, the array is sorted in increasing order.

Let us help you with an example of the increasing order array and finding the largest element.

Code:

#include <iostream>
using namespace std;
int main() {
    // Increasing order array of size 6
    int arr[] = {2,4,5,7,9,10};

    int size = 6;
    cout<<"Largest Element: "<< arr[size-1];
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Larget Element: 10

You can try by yourself with the help of online C++ Compiler .

Time Complexity: Since we are not traversing the whole array, its time complexity is O(1).

Space complexity: No space is utilized; hence space complexity is O(1).

We can compare the first and last element of the array if we are not given the order of sorting. Consider the example given below:

Code:

#include <iostream>
using namespace std;
int main() {
    // Increasing order array of size 6
    int arr[] = {2,4,5,7,9,10};


    int size = 6;
    // Compare first and last element to get the order
    int largest = arr[0] > arr[size-1] ? arr[0] : arr[size-1];
    cout<<"Largest Element: "<< largest;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Largest Element: 10

Time Complexity: No traversal through the whole array makes the time complexity O(1).

Space Complexity: Since no space is utilized, space complexity is also O(1).

Largest element in an array (Unsorted)

It is not common in interviews to be given a sorted array to find the largest element. Therefore, we shall learn to find the largest element in an array if it is unsorted.

Approach 1: Searching linearly

We will first assume that our first element is the largest. We will compare every other array element with the largest element and update it accordingly.

Let us see an example for a better understanding.

Code:

#include <bits/stdc++.h>
using namespace std;
 
// returns maximum in arr[] of size n
int largest(int arr[], int size)
{
    int i;
     
    // Assume first largest element as the 
    int largest = arr[0];
 
    // Traverse and compare every other element
    // Update the largest if any element is larger
    for (i = 1; i < size; i++)
        if (arr[i] > largest)
            largest = arr[i];
 
    return largest;
}
 
int main()
{
    int arr[] = {23, 43, 12, 55, 122, 100};
    int size = sizeof(arr)/sizeof(arr[0]);
    cout <<"The largest element in the array: "<< largest(arr, size);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

The largest element in the array: 122

Time Complexity: O(n), where n is the number of elements in the array.

Space complexity: Since no space is utilized, space complexity is O(1).

Approach 2: Searching via Divide and Conquer

Another option is to use the divide and conquer tactic. We will partition the array into two equal halves and recursively determine the greatest of those portions, similar to the merge sort. Then, to determine the largest element, compare the maximum of those portions.

Steps

1. Create a recursive function that takes the array as an argument along with its start and end indexes.
2. The most common scenarios will be
   1. Return the element as the max if the array size is 1.
   2. If the array size is two, compare the two elements and return the highest.
3. The part that recurses is
   1. Calculate and save the maximum left and right portions recursively.
   2. Using two comparisons, determine the largest among them.
4. Return the maximum value.
    

Code:

#include <iostream>


int findMax(int A[], int start, int end)
{
    int max;
    if ( start == end )
    {
        max = A[start];
    }
    else if ( start + 1 == end )
    {
        if ( A[start] < A[end] )
        {
            max = A[end];
        }
        else
        {
            max = A[start];
        }
    }
    else
    {
        int mid = start + (end - start)/2;
        int left = findMax(A, start, mid);
        int right = findMax(A, mid+1, end);
        if ( left > right )
            max = left;
        else
            max = right;
    }
    // Returning the max/ largest
   return max;
}
int main() {
    // Write C++ code here
    int arr[] = {45, 32, 12, 11, 50};
    int n = 5;
    std::cout<<”The largest element in the array: ”<<findMax(arr, 0, n-1);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

The largest element in the array: 50

Time complexity: O(N), since the worst case is the traversal of the whole array.

Space Complexity: O(log n), for using recursive stack.

Check out this problem - Next Smaller Element

FAQs

1. Is there any inbuilt function for finding the largest element in an array in C++?
   The function max_element(Array, Array+size),  defined in the header file algorithm, returns a reference to the largest element in an array passed as an array in the parameter.
    
2. How many comparisons do we have to make to find the largest element in an unsorted array linearly?
   N -1 comparisons are made to find the largest element in an unsorted array, where N is the number of elements in the array.
   
    
3. How many comparisons are there in the divide and conquer method?
   T(n) = 2 T(n/2) + 2
   T(2) = 1
   T(1) = 0
   Solving this recurrence relation, we get.
   if n is a power of 2
   T(n) = 3n/2 - 2
   Therefore, 3n/2 - 2 comparisons are made in this approach.
    
4. Can we find the smallest element in an array using the above methods?
   All the methods explained above can be tweaked to find the smallest instead of the largest of all. Instead of finding the largest, we find the smallest in a sorted array; instead of finding the maximum through the traversal of the array, we focus on the minimum, similarly, in divide and conquer we keep the comparison same just using the smallest value of both.

Key Takeaways

This article extensively discussed the most common approaches to finding the largest element in an array.

Recommended Reads: Permutation of string

Also read -  Decimal to Binary c++

We hope this blog has helped you enhance your knowledge. For learning more about coding in C++ or other problems like the Program To Print All Permutations Of A Given String or find a factorial of a number, check out Code Studio's blog site.

Recommended Problem - Merge K Sorted Arrays