DSA problem
Find Peak Element
A peak element is an element that is strictly greater than its neighbors. Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index of any one of them. You may imagine that nums[-1] = nums[n] = -∞. You must write an algorithm that runs in O(log n) time.
The O(log n) bound is the surprising part — peak finding sounds like it requires scanning everything, but it does not. The key invariant: at any window [lo, hi], if you look at mid and compare it to mid + 1, you can always discard one side. If nums[mid] < nums[mid + 1], the right side is ascending out of mid; somewhere to the right there must be a peak (eventually the sequence has to descend or hit the virtual -∞ past index n - 1). Symmetrically, if nums[mid] > nums[mid + 1], a peak exists to the left of, or at, mid.
Use the lower-bound style binary search: lo = 0, hi = n - 1, loop while lo < hi. Inside, compute mid = lo + (hi - lo) / 2, then branch on the comparison between nums[mid] and nums[mid + 1]. If the right neighbor is larger, set lo = mid + 1; otherwise hi = mid. When the loop ends, lo == hi is an index of a peak.
The reason mid + 1 cannot run off the array is that hi starts at n - 1 and only ever decreases; mid < hi whenever lo < hi, so mid + 1 <= hi <= n - 1. The whole search runs in O(log n) time and O(1) space.
Examples
nums = [1,2,3,1]2nums = [1,2,1,3,5,6,4]5 (or 1)nums = [1]0Constraints
- 1 <= nums.length <= 1000
- -2^31 <= nums[i] <= 2^31 - 1
- nums[i] != nums[i + 1] for all valid i.
- You must write an O(log n) algorithm.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.