Find Peak Element
Problem
A peak is an element strictly greater than its neighbours. Imagine nums[−1] = nums[n] = −∞, and no two adjacent elements are equal. Return the index of any peak, in O(log n) time.
Example 1
Input: [1, 2, 3, 1] Output: 2
Example 2
Input: [1, 2, 1, 3, 5, 6, 4] Output: 1 or 5
Test cases
Case 1
Input: [1,2,3,1] Expected (any of): [2]
Case 2
Input: [1,2,1,3,5,6,4] Expected (any of): [1,5]
Case 3
Input: [1] Expected (any of): [0]
View solutionHide solution1 approach
1. Binary search on the slope
Time O(log n)Space O(1)
If nums[mid] < nums[mid + 1] a peak lies to the right (the sequence must come down eventually); otherwise one lies at mid or to the left.
function findPeakElement(nums) { let lo = 0, hi = nums.length - 1; while (lo < hi) { const mid = (lo + hi) >> 1; if (nums[mid] < nums[mid + 1]) lo = mid + 1; else hi = mid; } return lo;}