Objective : In this article we will discuss an algorithm to Find a peak element in a Given Array. We will see the recursion techniques to solve this problem.
Peak Element: peak element is the element which is greater than or equal to both of its neighbors.
Input: Array, arrA[] .
Output: A peak element and its index
Approach:
A simple approach is to do a linear scan to a array and using few variables we can find a peak element. But the Time Complexity will be O(n) but real question is, Can we do better?
The Answer is yes, by using Binary Search techniques.
- If middle element is the peak element, return it
- If middle element is smaller than its left element , we will get our peak element on the left half
- If middle element is the smaller than its right element, we will our peak element on the right.
Time Complexity : O(logN)
Notes:
- If array has all the same elements, every element is a peak element.
- Every array has a peak element.
- Array might have has many peak elements but we are finding only one.
- If array is in ascending or descending order then last element or the first element of the array will be the peak element respectively.
Complete Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //we will use binary search techniques | |
| //if middle element is the peak element, return it | |
| //if middle element is smaller than its left element , we will get our peak element on the left half | |
| //if middle element is the smaller than its right element, we will our peak element on the right. | |
| public class PeakElement { | |
| public int peak(int [] arrA,int low, int high, int size){ | |
| int mid = (low+high)/2; | |
| if((mid==0||arrA[mid]>=arrA[mid–1]) && (arrA[mid]>=arrA[mid+1]||mid==size–1)){ | |
| return mid; | |
| } | |
| else if(mid>0 && arrA[mid]<arrA[mid–1]) return peak(arrA,low,mid–1,size); | |
| else return peak(arrA,mid+1,high,size); | |
| } | |
| public static void main(String args[]){ | |
| PeakElement pe = new PeakElement(); | |
| int arrA[] = { 1,2,3,4,0,1,5,4,3,2,1}; | |
| int peakEle = pe.peak(arrA, 0, arrA.length–1, arrA.length); | |
| System.out.println("Peak Element is found at index [" + peakEle +"] = "+ arrA[peakEle]); | |
| } | |
| } |
Output:
Peak Element is found at index [6] = 5
Here is video on finding a peak element in an array: https://www.youtube.com/watch?v=a7D77DdhlFc
Here is a video on finding a peak element in an array: https://www.youtube.com/watch?v=a7D77DdhlFc