Find Peak Element
On this page
Problem statement
Given an array where no two neighbours are equal, return the index of any peak: an element strictly greater than its neighbours. Positions outside the array count as −∞, so the first and last elements can be peaks. Your algorithm must run in O(log n) time.
It surprises many people that binary search works on an unsorted array. The key is that you don't need sorted data, only a rule that tells you which half definitely contains an answer. Original problem: LeetCode 162.
Example

Input: [1, 2, 1, 3, 5, 6, 4]
Output: 1 or 5
Input: [1, 2, 3]
Output: 2 # the last element is a peak: its right neighbour is −∞
Constraints (assumed)
- 1 ≤ n ≤ 1,000 (the method works for any n).
nums[i] != nums[i + 1]for all valid i.
What this question tests
- Using binary search on a condition, not on sorted values.
- Arguing why the half you keep must contain a peak.
- Writing a loop that always terminates and never reads out of bounds.
Questions to ask first
- Any peak, or the highest? (Here: any. The highest needs O(n).)
- Can neighbours be equal? (Here: no. With plateaus the halving argument breaks.)
- What happens at the edges? (Outside counts as −∞, so edges can be peaks.)
- Is O(n) acceptable? (No; O(log n) is required.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.