Find the Peak element from an array

In the given input array of integers find a peak element

In an array an element is a peak element, if the element is greater than both the neighbours.

For corner elements, we can consider the only neighbour present.

Example

a) Input array: [7, 11, 17, 33, 21, 19]
Output: 33
Neighbours of 33 are 21 and 17.
33 is greater than 21 and17,
Therefore, 33 is peak element.

b) Input array: [1, 2, 3, 4, 5, 6, 7]
Output: 7
Neighbour of 7 is only 5. (corner element)
7 is greater than 5
Therefore, 7 is peak element.

c) Input array: [45, 35, 25, 15, 5]
Output: 45
Neighbour of 45 is only 35. (corner element)
45 > 35,
Therefore, 33 is peak element.

d) Input array: [5, 19, 24, 14, 8, 4, 26, 12]
Output: 24 or 26
Here,
Neighbours of 24 are 19 and 14 and Neighbours of 26 are 4 and 12.
24 is greater than 19 and 14, 26 is greater than 4 and 12.
Therefore, 24 and 26 are both peak elements.
Return anyone of 24 and 26.

Algorithm

Time Complexity: O(logn)

We can do a linear search to find element which is greater than both of its neighbours. But, it takes O(n) time. So, we use divide and conquer method to find peak in O(logn) time.

Here we do a modified binary search,

a. If middle element is greater than both neighbours then we return the middle element.
b. If the middle element is smaller than the left neighbour, then peak element must be in left half of the array.
c. If the middle element is smaller than the right neighbour, then peak element must be in right half of the array.

Algorithm working

C++ Program

#include <bits/stdc++.h>

using namespace std;

//Function to find peak element
//Modified Binary search
int FindPeak(int array[], int low, int high, int n)
{
    int mid = low + (high - low)/2;
    //return mid 
    //If mid is greater than neighbours or mid = 0
    //If neighbours exist
    if((mid == 0 || array[mid-1] <= array[mid]) && (mid == n-1 || array[mid+1] <= array[mid]))
    {
        return mid;
    }
    //If mid is not peak and its right neighbour is greater.
    //then search in right half 
    else if(mid > 0 && array[mid-1] < array[mid])
    {
        return FindPeak(array, (mid + 1), high, n);
    }
    //If mid is not peak and its left neighbour is greater.
    //then search in left half
    else
    {
        return FindPeak(array, low, (mid -1), n);
    }
}
 
//Main function
int main()
{
    int input_array[] = {1, 3, 20, 4, 1, 0};
    int n = sizeof(input_array)/sizeof(int);
    int result = FindPeak(input_array, 0, n-1, n);
    cout<<"Index of peak element is "<< result<<endl;
    cout<<"Peak element is "<<input_array[result]<<endl;
    return 0;
}