In this article, we have explained the problem of finding Peak Element in an Array along with different approaches to solve it efficiently.

Table of contents:

1. Problem statement: Peak Element in an Array
2. The Linear Search Approach
3. Divide and Conquer Approach

Let us get started with Peak Element in an Array.

Problem statement: Peak Element in an Array

The peak element in an array is an array element which is not smaller than it's neighbours. For example, given an array of {6,7,10,12,9} 12 is the peak element of the array. Another example is an array of {8,15,9,2,23,5} in this case, there are two peak elements:15 and 23.

However, there are some edge cases to be considered.

• One edge case can be when all elements in the array are the same such as {5,5,5}. The peak element is 5.
• The second edge case to consider is when the elements in the array are sorted in descending order i.e from the highest to the lowest.{50,40,30,20}.50 is the peak element.
• The final edge is elements in an array sorted in ascending order i.e the lowest element to the highest element {20,30,40,50,70,90}. The peak element is 90.

The peak element of an array can be found using the naive approach of linear search with time complexity O(N) or the optimized divide and conquer approach with time complexity O(logn). In this article, we will discuss both approaches in detail.

The Linear Search Approach

How it works & Implementation

In this approach we travers through the array and compare elements with it's neighbours. Once a peak element is found, it's immediately returned.

How it works:

• Loop through the array say arr[]={2,5,7,8,6} If in the first element is greater than the second or the last element is greater than the second last return the element
• Else continue traversing the array from the next index i.e from second index to the last but one index.
• If an element arr[i] in the array is greater than both its neighbours arr[i-1] and arr[i+1], then return the element

Implementation In Java

The lines of code below returns the peak element in a given array.

int findPeakELement(int arr[], arrlength){
    if (arrlength == 1)
      return arr[0];//return the element if there's only one element in the array
    if (arr[0] >= arr[1])
        return arr[0];
    if (arr[arrlength - 1] >= arr[arrlength - 2])
        return arr[arrlength - 1];
 
    // find the peak in the remaining array elements
    for(int i = 1; i < arrlength - 1; i++)
    {
         //comparing current element with neighbours
        if (arr[i] >= arr[i - 1] &&
            arr[i] >= arr[i + 1])
            return arr[i];
    }
    return arr[0];
}

Time Complexity: O(N)

Divide and Conquer Approach

How it works & Implementation

How it works:

• Initialize two variables, start and end, initialize start = 0 and end = n-1, where n is the length of the array.
• Continue iterating until start <= end.
• Compare the middle element with it's neighbors.If it's greater than it's neighbours, return the index. index of mid = (start+end)/2.
• Else if the element on the left side of the middle element is greater than the middle element, iterate to the left of the array for the peak element.Hence, end = mid – 1
• Else if the element on the right side of the middle element is greater than the middle element, iterate to the right of the middle element to search for the peak. Hence,start = mid + 1.

For example, given an array of arr[]={4,5,7,6,8,9,10}.7 is the peak element. Now let's see how to find it. We initialize start=0 and end=length of array - 1. mid= (start + end)/2 i.e mid= 3 and arr[3]=6. We then compare arr[3] with it neighbors. arr[3] < arr[2], arr[3] < arr[4]. We find a new mid from the left. end= mid-1, start=0. mid=(0+2)/2, mid=1 arr[1]=5. Comparing arr[1] with it neighbors, arr[1]>arr[0] but arr[1]<arr[2]. We find a new mid from the right. start=mid+1, end=2, mid(2+2)/2,mid=2. arr[2]=7. Comparing arr[2] with it neighbours, arr[2] > arr[1] and arr[2]>arr[3]. Therefore, arr[2] is the peak element in the array so we return it index. Which is index 2.

Mid of the array will be 6. comparing 6 with it neighbors. We first compare with the left

Implementation in Java

The lines of code below returns the index of the peak element given an array num[]

public int findPeakElement(int[] num) {    
    return peakFinder(num,0,num.length-1);
}
public int peakFinder(int[] num,int start,int end){
    if(start == end){
        return start;
    }else if(start+1 == end){
        if(num[start] > num[end]) return start;
        return end;
    }else{
        int m = (start+end)/2;        
        if(num[m] > num[m-1] && num[m] > num[m+1]){
            return m;
        }else if(num[m-1] > num[m] && num[m] > num[m+1]){
            return peakFinder(num,start,m-1);
        }else{
            return peakFinder(num,m+1,end);
        } 
    }
}

Time Complexity: O(logN)

With this article at OpenGenus, you must have the complete idea of Find Peak Element in an Array.