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:
Output:
Peak Element is found at index [6] = 5
