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

Download   Run Code

Output:

The peak element is 10

Java

Download   Run Code

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

 

Download   Run Code

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 🙂
 

Get great deals at Amazon




Leave a Reply

Notify of
avatar
wpDiscuz