Modified Binary Search
LC #162Medium
Find Peak Element
Modified Binary Search
GoogleMetaMicrosoftAmazonBloombergProblem
A peak element is one that is strictly greater than its neighbors. Find any peak in O(log n).
arraybinary-search
Constraints
- ›1 ≤ nums.length ≤ 1000
- ›-2³¹ ≤ nums[i] ≤ 2³¹-1
- ›nums[-1] = nums[n] = -∞ (edges are valleys)
- ›O(log n) required
Example
Input
nums = [1, 2, 3, 1]Output
2Why
nums[2] = 3 is a peak since nums[1] < nums[2] > nums[3]