# Find peak element in an array

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

Output:

The peak element is 10

## Java

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 -

Output:

The peak element is 14

(2 votes, average: 5.00 out of 5)