To solve the problem of finding a peak element in an array, we need to understand what a peak means. A peak is simply an element that is not smaller than its neighbors. That means for any index i
, arr[i]
is a peak if:
- It is the first element and
arr[i] ≥ arr[i+1]
- It is the last element and
arr[i] ≥ arr[i-1]
- It is in the middle and
arr[i] ≥ arr[i-1]
and arr[i] ≥ arr[i+1]
So how do we find such an element efficiently? Let's walk through different scenarios:
📍 Case 1: The array has only one element
Any single element is trivially a peak because it has no neighbors to compare with. So, the only element is the peak.
📍 Case 2: The peak is at the beginning or end
If the first element is greater than the second, it's a peak. Similarly, if the last element is greater than the second last, it's also a peak.
📍 Case 3: The peak is somewhere in the middle
We can use a binary search approach. At each step, we look at the middle element arr[mid]
and compare it with its neighbors:
- If
arr[mid]
is greater than or equal to both neighbors, then it is a peak.
- If
arr[mid]
is smaller than its right neighbor, then there must be a peak on the right side (because the values are increasing).
- If
arr[mid]
is smaller than its left neighbor, then there must be a peak on the left side (because the values are increasing in that direction).
By following this process, we can efficiently reach a peak without scanning every element. The time complexity is O(log n), which is optimal for this problem.
📍 Case 4: The array is empty
If the array is empty, there are no elements to evaluate, so we return -1
to indicate that no peak exists.
Since the problem only asks for any one peak, and not necessarily the greatest one, we can stop as soon as we find a valid peak index using this logic.