Find Peak Element
Given an integer array nums, find a peak element and return its index. A peak element is strictly greater than its neighbors. You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered greater than a neighbor outside the array boundary. The array is guaranteed to have at least one peak. If multiple peaks exist, return the index of any one of them. You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [1,2,3,1]
Output: 2
Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 5
- 1 <= nums.length <= 1000
- -2^31 <= nums[i] <= 2^31 - 1
- nums[i] != nums[i+1] for all valid i
Approach: Binary Search
Compare the middle element with its right neighbor. If nums[mid] > nums[mid + 1], a peak must exist in the left half (including mid) since values are decreasing. Otherwise, a peak exists in the right half. The boundary conditions guarantee at least one peak on each side of any descent.
function findPeakElement(nums) {
let left = 0, right = nums.length - 1;
while (left < right) {
const mid = (left + right) >> 1;
if (nums[mid] > nums[mid + 1]) right = mid;
else left = mid + 1;
}
return left;
}
Time Complexity: O(log n)
Space Complexity: O(1)
Saved in this browser only. Private to you.