Pattern this teaches:Binary Search on Sorted Data
Find Peak Element
A medium Binary Search interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Binary Search
- Sheets
- 2
- Core for
- 7 roles
The problem
Given an integer array, find a peak element and return its index. A peak element is one that is strictly greater than its neighbors. If the array contains multiple peaks, return the index of any of them.
Example 1
- Input
- nums = [2,5,3,1]
- Output
- 1
- Why
- 5 at index 1 is the only peak (5 > 2 and 5 > 3).
Example 2
- Input
- nums = [1,2,3,2,1]
- Output
- 2
- Why
- 3 at index 2 is the only peak (3 > 2 and 3 > 2).
Constraints
- 1 <= nums.length <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
- nums[i] != nums[i + 1] for all valid i
How to think about it
Updated 2026-09-29You do not need an entirely sorted collection to discard half the search area. Stepping in the direction of an upward slope is guaranteed to lead to a local peak eventually, because out-of-bounds values act as negative infinity and adjacent values are never equal.
Approaches, worst first
Linear neighbor scan
time O(n) · space O(1)
Iterate across the array and check if the current number exceeds both adjacent values. Simple and requires zero assumptions, but evaluates items sequentially instead of exploiting downhill guarantees.
Binary search on slopeWrite this one
time O(log n) · space O(1)
Compare mid against mid + 1. If mid is strictly less than mid + 1, a rising slope guarantees at least one peak in the right half, so set low = mid + 1. Otherwise, a peak must exist at mid or to its left, so high = mid.
Where people lose marks · 3
- Checking mid - 1 without checking for index zero causes array index out-of-bounds errors; comparing mid with mid + 1 keeps index lookups safe when low < high.
- Using high = mid - 1 when mid itself could be the actual peak skips the answer; shrink the upper bound to mid rather than mid - 1.
- Looping with low <= high while setting high = mid causes an infinite loop when low equals high.
The theory behind it
Binary Search — the ground this problem stands on. All Binary Search problems
What Binary Search is
Binary search is the guessing strategy used when searching a thick telephone directory or guessing a secret number between one and a hundred. Rather than inspecting names one by one from the first page, the search opens straight to the middle page. If the target precedes that middle entry, the entire back half is discarded; if it follows, the front half is eliminated. Repeating this halved split finds the item with remarkable speed.
When to reach for it
Reach for binary search when queries target sorted collections, rotated sorted arrays, or monotonic answer spaces. Strong hints include logarithmic time constraints like O(log n) or search ranges exceeding one billion where stepping one value at a time times out. It also applies when validating whether a guessed solution is possible via a monotonic boolean check, known as binary search on answer.
How the pattern works
Define the search territory with two inclusive pointers, low and high. Compute the midpoint using low plus half the difference to high, avoiding integer overflow. Formulate an exact boolean condition that divides the range into true and false halves. Decide whether the boundary condition includes the midpoint or shifts strictly past it. The loop invariant states that the sought target, if it exists, remains trapped inside the interval throughout every iteration.
More Binary Search problems
Target Roles
Core requirement for 7 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .