How Do You Find a Peak Element in an Array?
Learn how binary search finds a peak element in O(log n) time by comparing neighbors, and how to answer this interview question.
Expected Interview Answer
A peak element — one strictly greater than both its neighbors, with -infinity assumed beyond the array's edges — can be found in O(log n) using binary search: at each mid, compare nums[mid] to nums[mid+1], and move toward the larger side, since that side is guaranteed to contain a peak.
The key insight is that any array has at least one peak, because the array's boundaries act as -infinity, so if you keep walking uphill you must eventually hit a local maximum. At each step of the binary search, if nums[mid] < nums[mid+1], the array is still ascending at mid, so a peak must exist somewhere to the right (search right by setting left = mid + 1); otherwise nums[mid] >= nums[mid+1] means a peak exists at mid or to its left (search left by setting right = mid). This is not a search for a specific value, so standard binary search comparisons against a target do not apply — the comparison is always against the neighbor, not a target. The loop terminates when left == right, which is guaranteed to be a valid peak index.
- O(log n) time, far better than the O(n) linear scan
- O(1) extra space, purely pointer-based
- Works correctly for any array shape without needing global sortedness
- Guaranteed to terminate at a valid peak due to the -infinity boundary argument
AI Mentor Explanation
Finding a peak run-rate over in a match graph is like scanning the innings for an over that scored more than both the over immediately before and immediately after it, treating the innings' start and end as scoring zero. Instead of checking every over one by one, you jump to the middle over and compare it with the very next over; if the next over scored more, a peak must exist somewhere further along that upward trend, so you search that side. If the next over scored less or equal, the current or earlier overs must contain a peak, so you search that side instead, halving the overs to check every single time. This mirrors binary search exactly, except you compare against a neighboring over's score rather than a fixed target score.
Step-by-Step Explanation
Step 1
Set up binary search bounds
Initialize left = 0, right = n - 1, treating positions beyond the array as -infinity.
Step 2
Compare mid to its right neighbor
Compute mid; if nums[mid] < nums[mid+1], the array is ascending at mid, so a peak lies to the right.
Step 3
Move toward the ascending side
If ascending, set left = mid + 1; otherwise (nums[mid] >= nums[mid+1]) set right = mid, since a peak is at or before mid.
Step 4
Terminate when left equals right
The loop ends when left == right, and that index is guaranteed to be a valid peak.
What Interviewer Expects
- Explain why a peak is guaranteed to exist using the -infinity boundary argument
- Correctly compare nums[mid] with nums[mid+1], not with a fixed target
- State O(log n) time and O(1) space
- Recognize this is not a search for a specific value, unlike classic binary search
Common Mistakes
- Comparing nums[mid] to nums[mid-1] and nums[mid+1] simultaneously instead of just the right neighbor, complicating the logic unnecessarily
- Assuming a peak must be a global maximum rather than any local peak
- Using left <= right with mid+1 access going out of bounds without proper loop condition (left < right) handling
- Assuming the array must be sorted or unsorted in a particular way; peak-finding works on arbitrary arrays
Best Answer (HR Friendly)
“To find a peak element, I use binary search, but instead of comparing against a target value, I compare each middle element to its right neighbor. If the next element is bigger, I know a peak exists further to the right, so I search there; otherwise a peak exists at or before the middle, so I search left. Because the edges of the array count as negative infinity, a peak is always guaranteed to exist, which is what makes this binary search approach valid.”
Code Example
def find_peak_element(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] < nums[mid + 1]:
left = mid + 1
else:
right = mid
return left # index of a peak element
print(find_peak_element([1, 2, 1, 3, 5, 6, 4])) # 1 or 5, both valid peaksFollow-up Questions
- How would you find a peak element in a 2D grid instead of a 1D array?
- How would this change if the array could contain adjacent equal elements?
- How would you find all local peaks instead of just one?
- Why does this binary search work even though the array is not globally sorted?
MCQ Practice
1. What defines a peak element in this problem?
A peak is a local maximum — strictly greater than both neighbors, with out-of-bounds neighbors treated as -infinity.
2. Why is a peak element guaranteed to exist in any array?
Treating the edges as -infinity means any strictly ascending walk must terminate at a point higher than both neighbors.
3. What comparison drives the binary search direction when finding a peak element?
If nums[mid] < nums[mid+1], the search moves right since a peak must exist along the ascending direction; otherwise it moves left.
Flash Cards
What is a peak element? — An element strictly greater than both its neighbors, with array edges treated as -infinity.
Why is a peak guaranteed to exist in any array? — Because the -infinity boundaries mean any ascending trend must eventually hit a local maximum.
What comparison decides binary search direction for peak finding? — Comparing nums[mid] with nums[mid + 1], not with a fixed target.
What is the time complexity of peak-finding via binary search? — O(log n), since half the array is discarded each iteration.