Find the Peak Element from an Array

Problem Statement

In the “Find the Peak Element from an Array” problem we have given an input array of integers. Find a peak element. In an array, an element is a peak element, if the element is greater than both the neighbours. For corner elements, we can consider the only neighbour present.

Input Format

The first and only one line containing an integer N.

Second-line containing N space-separated integers.

Output Format

The first and only one line containing an integer which denotes the Peak Element of the Array.

Constraints

• 1<=N<=10^5
• -10^9<=N<=10^9

Example

6
7 11 17 33 21 19

33

Explanation: Neighbours of 33 are 21 and 17. 33 is greater than 21 and17, Therefore, 33 is peak element.

7
1 2 3 4 5 6 7

7

Explanation: The neighbour of 7 is only 5(corner element). 7 is greater than 5 Therefore, 7 is the peak element.

5
45 35 25 15 5

45

Explanation: The neighbour of 45 is only 35(corner element). 45 > 35, Therefore, 33 is the peak element.

8
5 19 24 14 8 4 26 12

24

Explanation: Here, Neighbours of 24 are 19 and 14 and Neighbours of 26 are 4 and 12. 24 is greater than 19 and 14, 26 is greater than 4 and 12. Therefore, 24 and 26 are both peak elements. We print 24 as our answer. We can also print 26 which is also a valid answer.

Algorithm to Find the Peak Element from an Array

We can do a linear search to find the element which is greater than both of its neighbours. But, it takes O(n) time. So, we use the divide and conquer method to find a peak in O(logn) time. Here we do a modified binary search-

a. If the middle element is greater than both neighbours then we return the middle element.
b. If the middle element is smaller than the left neighbour, then the peak element must be in the left half of the array.
c. If the middle element is smaller than the right neighbour, then peak element must be in right half of the array.

Implementation

C++ Program to Find the Peak Element from an Array

#include <bits/stdc++.h>
using namespace std;

//Function to find peak element
//Modified Binary search
int FindPeak(int array[], int low, int high, int n)
{
    int mid = low + (high - low)/2;
    //return mid 
    //If mid is greater than neighbours or mid = 0
    //If neighbours exist
    if((mid == 0 || array[mid-1] <= array[mid]) && (mid == n-1 || array[mid+1] <= array[mid]))
    {
        return mid;
    }
    //If mid is not peak and its right neighbour is greater.
    //then search in right half 
    else if(mid > 0 && array[mid-1] < array[mid])
    {
        return FindPeak(array, (mid + 1), high, n);
    }
    //If mid is not peak and its left neighbour is greater.
    //then search in left half
    else
    {
        return FindPeak(array, low, (mid -1), n);
    }
}

int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int index = FindPeak(a, 0, n-1, n);
    cout<<a[index]<<endl;
    return 0;
}

Java Program to Find the Peak Element from an Array

import java.util.Scanner;
class sum
{
    //Function to find peak element
    //Modified Binary search
    public static int FindPeak(int array[], int low, int high, int n)
    {
        int mid = low + (high - low)/2;
        //return mid 
        //If mid is greater than neighbours or mid = 0
        //If neighbours exist
        if((mid == 0 || array[mid-1] <= array[mid]) && (mid == n-1 || array[mid+1] <= array[mid]))
        {
            return mid;
        }
        //If mid is not peak and its right neighbour is greater.
        //then search in right half 
        else if(mid > 0 && array[mid-1] < array[mid])
        {
            return FindPeak(array, (mid + 1), high, n);
        }
        //If mid is not peak and its left neighbour is greater.
        //then search in left half
        else
        {
            return FindPeak(array, low, (mid -1), n);
        }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int index = FindPeak(a, 0, n-1, n);
        System.out.println(a[index]);
}

8 
5 19 24 14 8 4 26 12

24

Complexity Analysis to Find the Peak Element from an Array

Time Complexity

O(logN) where N is the size of the given array. Here we use the concept of binary search which lead us to logN time complexity.

Space Complexity