Given an array, find peak element in it. A peak element is an element that is greater than its neighbors.

An element A[i] is a peak element if it is not smaller than its neighbor(s)

A[i-1] <= A[i] <= A[i+1] for 0 <= i <= N-1

A[i-1] <= A[i] if i = N - 1

A[i] <= A[i+1] if i = 0

There might be multiple peak element in a array, we need to find any peak element.

For example,

**Input : **[8, 9, 10, 2, 5, 6]

**Output: **The peak element is 10

**Input : **[8, 9, 10, 12, 15]

**Output: **The peak element is 15

**Input : **[10, 8, 6, 5, 3, 2]

**Output: **The peak element is 10

**Naive solution** would be to test all elements for peak by running a **linear search** on the array and return the element that is greater than its neighbors. Two special cases we need to handle. If the array is sorted in descending order, its peak element is the first element. If the array is sorted in ascending order, the peak element is the last element. The problem with this approach is that its worst case time complexity is O(n).

We can easily solve this problem in O(log(n)) time by using an idea similar to **binary search**. We calculate the mid index and if the mid element is greater than both of its neighbors, then we return the element as it is a peak. If the right neighbor of mid is greater than the mid element, then we find the peak recursively in the right side of the array. If the left neighbor of mid is greater than the mid element, then we find the peak recursively in the left side of the array.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include <iostream> using namespace std; // Recusive function to find peak in the array int findPeakElement(int A[], int low, int high, int n) { // find mid element int mid = (low + high) / 2; // check if mid element is greater than its neighbors if ((mid == 0 || A[mid - 1] <= A[mid]) && (mid == n - 1 || A[mid + 1] <= A[mid])) return mid; // If the left neighbor of mid is greater than the mid element, // then find the peak recursively in the left sub-array if (mid - 1 >= 0 && A[mid - 1] > A[mid]) return findPeakElement(A, low, mid - 1, n); // If the right neighbor of mid is greater than the mid element, // then find the peak recursively in the right sub-array return findPeakElement(A, mid + 1, high, n); } // main function int main() { int A[] = { 8, 9, 10, 2, 5, 6 }; int n = sizeof(A) / sizeof(A[0]); int index = findPeakElement(A, 0, n - 1, n); cout << "The peak element is " << A[index]; return 0; } |

**Output: **

The peak element is 10

**Time complexity** of above solution is O(log(n)).

**Auxiliary space** used by the program is O(1).

**STL implementation using adjacent_find()** –

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <bits/stdc++.h> using namespace std; // Function to find peak element of the array int findPeakElement(vector<int> data) { auto peak = adjacent_find(data.begin(), data.end(), greater<int>()); if (peak == data.end()) { // to handle when array is sorted in ascending order, // re-position to last element --peak; } return *peak; } // main function int main() { vector<int> data { 6, 8, 9, 14, 10, 12}; cout << findPeakElement(data); return 0; } |

**Output: **

14

**References:**

http://stackoverflow.com/questions/16933543/peak-element-in-an-array-in-c

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply