TL;DR
Binary search on the slope (climb toward the rising side) — O(log n) time, O(1) space.
Approach 1 — Brute force (scan for a peak)
Check each element against its neighbors; with −∞ beyond the ends, the first index where the sequence stops rising is a peak.
class Solution:
def findPeakElement(self, nums: list[int]) -> int:
n = len(nums)
for i in range(n):
left_ok = i == 0 or nums[i - 1] < nums[i]
right_ok = i == n - 1 or nums[i] > nums[i + 1]
if left_ok and right_ok:
return i
return -1 # unreachable: a peak always exists
In fact the first i with nums[i] > nums[i + 1] (or the last index) is always a peak, so one forward pass suffices. Time O(n), space O(1). Fine at n <= 1000, but the problem demands O(log n) — the whole point is realizing an unsorted array can still be halved.
Approach 2 — Iterative binary search on the slope
The insight: a peak is guaranteed to exist on the uphill side of any element. If nums[mid] < nums[mid + 1], walk uphill to the right: either values rise forever until the last element (a peak, since beyond it is −∞) or they stop rising somewhere — and that turning point is a peak. Symmetrically, if nums[mid] > nums[mid + 1], a peak exists at mid or to its left. So one comparison of mid with its right neighbor discards half the array — binary search without any sortedness, powered by an existence invariant: the interval [lo, hi] always contains a peak.
class Solution:
def findPeakElement(self, nums: list[int]) -> int:
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < nums[mid + 1]:
lo = mid + 1 # uphill to the right: peak lives there
else:
hi = mid # falling here: mid or left holds a peak
return lo
Walkthrough on nums = [1, 2, 1, 3, 5, 6, 4]:
lo=0, hi=6 → mid=3, nums[3]=3 < nums[4]=5 → lo=4.lo=4, hi=6 → mid=5, nums[5]=6 > nums[6]=4 → hi=5.lo=4, hi=5 → mid=4, nums[4]=5 < nums[5]=6 → lo=5.lo == hi == 5 → return 5, and nums[5]=6 is indeed a peak. ✓
Note mid + 1 is always in range because lo < hi guarantees mid < hi. Time O(log n), space O(1).
Approach 3 — Recursive binary search
The insight: the invariant “this interval contains a peak” recurses cleanly: look at the middle, commit to the uphill half, repeat until one element remains. This is the formulation from the classic divide-and-conquer treatment of peak finding (MIT 6.006’s opening example).
class Solution:
def findPeakElement(self, nums: list[int]) -> int:
def go(lo: int, hi: int) -> int:
if lo == hi:
return lo
mid = (lo + hi) // 2
if nums[mid] < nums[mid + 1]:
return go(mid + 1, hi)
return go(lo, mid)
return go(0, len(nums) - 1)
Walkthrough on nums = [1, 2, 3, 1]:
go(0, 3): mid=1, nums[1]=2 < nums[2]=3 → go(2, 3).go(2, 3): mid=2, nums[2]=3 > nums[3]=1 → go(2, 2).go(2, 2): lo == hi → return 2. ✓
Time O(log n), space O(log n) recursion stack — same comparisons as Approach 2, worth knowing as the textbook phrasing.
Common pitfalls
- Trying to verify “is
mid a peak” with both neighbors and handling four cases — comparing only mid vs mid + 1 is enough and needs no boundary special-casing (the lo < hi condition keeps mid + 1 valid).
- Using
hi = mid - 1 on the falling branch: when nums[mid] > nums[mid + 1], mid itself may be the peak; stepping past it can converge on a non-peak.
- Assuming the array must first be sorted or unimodal — the guarantee that adjacent elements differ plus the −∞ borders is all the structure needed, and any peak is accepted.
- Overthinking multiple peaks: the algorithm finds a peak, not the global maximum. Returning the max element’s index costs
O(n) and is exactly the trap.
Pattern takeaway
Binary search generalizes beyond sorted arrays: it works whenever you can maintain an invariant — “the answer exists in [lo, hi]” — and make one local comparison that shrinks the interval while preserving the invariant. Here the local slope points toward a guaranteed peak. When a problem grants O(log n) on unsorted data, hunt for that kind of half-eliminating local test.