Find the Peak Element
Given an array nums , find its peak element and return its index (0-based indexing).
A peak element is one that is strictly greater than its neighbors. If there are multiple peaks, you may return the index of any one of them.
It is guaranteed that at least one peak element exists in the given input array.
You should write an algorithm that runs in O(log n) time.
Examples
Input: nums = [1] Output: 0 Explanation: Single element 1 at index 0 is the peak. Input: nums = [1, 2, 3, 4, 5] Output: 4 Input: nums = [1, 2, 1, 3, 5, 6, 4] Output: 1 or 5
We use a binary search technique rather than a linear scan to achieve logarithmic time complexity, taking advantage of the properties of the peak.
The input array can be viewed as alternating ascending and descending sequences. Using this property, a modified binary search efficiently finds any peak element.
Algorithm
- Calculate the middle element mid.
- If nums[mid] is greater than nums[mid + 1] (descending slope), the peak lies at or to the left of mid, so move the search to the left half.
- If nums[mid] is less than nums[mid + 1] (ascending slope), the peak lies to the right of mid, so move the search to the right half.
- Repeat this process, reducing the search space until only one element remains — this element is the peak.
from typing import List
def find_peak_element(nums: List[int]) -> int:
l = 0
r = len(nums)-1
while l<r:
mid = (l+r)//2
if nums[mid]>nums[mid+1]:
r = mid
else:
l = mid+1
return lTime Complexity: O(log n). Because the search space halves each step.
Space Complexity: O(1). The algorithm uses only a fixed number of variables (l, r, m).