Binary Search · LC #162
Find Peak Element
Find any peak element in an array (strictly greater than its neighbors) in O(log n) by following the ascending slope - any local maximum reachable via slope-following guarantees a peak exists in that direction.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
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 to any of the peak elements. You may imagine that `nums[-1] = nums[n] = -∞`. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array. You must write an algorithm that runs in O(log n) time.
Sample I/O
Input: nums = [1,2,3,1] Output: 2 Input: nums = [1,2,1,3,5,6,4] Output: 5 (index 1 is also valid)
Time: O(log n) · Space: O(1)
Intuition
How to Think About It
Intuition
If `nums[mid] < nums[mid+1]`, the slope is rising to the right, so a peak must exist in `[mid+1, r]` - the right half is guaranteed to contain a local maximum. Conversely, if `nums[mid] > nums[mid+1]`, a peak exists in `[l, mid]`. This eliminates half the space at each step.
Core Concept
Use `l < r` (not `l <= r`) because we compare `mid` with `mid+1` - at `l == r` there is only one candidate. Set `r = mid` when `nums[mid] > nums[mid+1]` (peak is here or left), `l = mid+1` when ascending. When loop exits, `l == r` is the peak index.
When to use
Finding any local maximum/minimum in O(log n); "find any valid answer" problems where the predicate is directional (slope-based).
When NOT to use
When you need the global maximum (use linear scan); when array has equal adjacent elements (strict inequality breaks).
Key Insights
What to Know Cold
- Loop condition is `l < r`, not `l <= r` - avoids out-of-bounds `mid+1` access when `l == r`.
- When `nums[mid] > nums[mid+1]`, set `r = mid` (not `mid-1`) because `mid` itself could be the peak.
- The boundary assumption `nums[-1] = nums[n] = -∞` means the first and last elements can be peaks.
- Any ascending slope is guaranteed to lead to a peak before the boundary (by the intermediate value analogue for discrete arrays).
- This same slope-following trick appears in "Find Minimum in Mountain Array" and LC 852.
3 examples
Worked Examples
Single peak at end of ascending run
nums=[1,2,3,1].
l=0,r=3. mid=1→nums[1]=2<nums[2]=3→l=2. mid=2→nums[2]=3>nums[3]=1→r=2. l==r=2→return 2.
function findPeakElement(nums: number[]): number {
let l=0, r=nums.length-1;
while(l<r){
const m=l+Math.floor((r-l)/2);
if(nums[m]>nums[m+1]) r=m;
else l=m+1;
}
return l;
}Output: 2
Canonical case showing slope-following termination.
Multiple peaks - return any
nums=[1,2,1,3,5,6,4].
Binary search follows ascending slope to index 5 (value 6); index 1 (value 2) is also valid.
Output: 5 (or 1)
Shows algorithm finds one valid peak among many - answer need not be unique.
Strictly descending array
nums=[5,4,3,2,1].
Every mid check: nums[mid] > nums[mid+1] → r shrinks to 0. First element is the peak.
Output: 0
Edge case: peak at index 0 (left boundary treated as -∞).