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

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 |
#include <stdio.h> // Recursive 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(void) { int A[] = { 8, 9, 10, 2, 5, 6 }; int n = sizeof(A) / sizeof(A[0]); int index = findPeakElement(A, 0, n - 1, n); printf("The peak element is %d", A[index]); return 0; } |

`Output:`

The peak element is 10

## Java

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 |
class PeakElement { // Recursive function to find peak element of the array public static int findPeakElement(int[] A, int left, int right) { // find mid element int mid = (left + right) / 2; // check if mid element is greater than its neighbors if ((mid == 0 || A[mid - 1] <= A[mid]) && (mid == A.length - 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, left, mid - 1); } // 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, right); } // main function public static void main(String[] args) { int[] A = { 8, 9, 10, 2, 5, 6 }; int index = findPeakElement(A, 0, A.length - 1); System.out.println("The peak element is " + A[index]); } } |

`Output:`

The peak element is 10

The time complexity of above solution is O(log(n)) and auxiliary space used by the program is O(1).

##### STL implementation using `std::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 <iostream> #include <vector> #include <algorithm> // Function to find peak element of the array int findPeakElement(std::vector<int> data) { auto peak = std::adjacent_find(data.begin(), data.end(), std::greater<>()); 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() { std::vector<int> data { 6, 8, 9, 14, 10, 12}; std::cout << "The peak element is " << findPeakElement(data); return 0; } |

`Output:`

The peak element is 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