Find the 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 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 –
 

Download   Run Code

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()
 

Download   Run Code

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

Notify of
avatar
wpDiscuz