Table of Contents

## 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

**O(1)** because we don’t use any auxiliary space at here.