← DSA Atlas
Dedicated problem page · #162

Find Peak Element

MediumBinary SearchBinary search toward the higher neighborBinary search
Solve on LeetCode ↗
162
MediumBinary SearchBinary searchBinary search toward the higher neighbor

Find Peak Element

Given an integer array nums where no two adjacent elements are equal, return the index of any peak element — an element strictly greater than both of its neighbors. Values just outside the array are treated as negative infinity. The algorithm must run in O(log n) time.

Open official problem prompt ↗
In plain English

Locate any local maximum in an array in logarithmic time without sorting or scanning it.

Picture it like this

Hiking in fog: you cannot see the summit, but if the ground rises to your right you step right, and if it falls you step left. Following the uphill direction always brings you to a peak.

Example
Input
nums = [1,2,3,1]
Output
2
Why
nums[2] = 3 is greater than its neighbors 2 and 1, so index 2 is a valid peak.
Constraints
1 <= nums.length <= 1000-2^31 <= nums[i] <= 2^31 - 1nums[i] != nums[i + 1] for all valid iImagined nums[-1] and nums[n] equal negative infinity
Pattern lesson

See the pattern, then code

Binary search toward the higher neighbor
Recognition clue

A request to find any peak in O(log n) despite the array being unsorted is the signature — you cannot sort, so you must exploit the slope direction.

↗
Binary Search

Sorted data or a monotonic true/false condition over a possible answer.. If nums[mid] < nums[mid+1] the slope rises to the right, so a peak must exist to the right; otherwise a peak exists at mid or to the left. Following the ascending neighbor always walks uphill toward a peak.

New words, made simpleKnow these before the algorithm
Peak / local maximum
An element strictly larger than both immediate neighbors
Slope direction
Whether the next element is higher or lower than the current one
Sentinel
The imagined negative infinity just beyond each array end
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Linear scan for a peak

Correct but violates the required O(log n) bound.

Walk left to right and return the first element greater than its neighbors.

Time O(n)Space O(1)
Best choiceBinary search on the slope

Meets the time bound and needs no extra memory.

Move toward whichever neighbor of mid is larger, guaranteeing a peak lies in that direction.

Time O(log n)Space O(1)
The rule we keep true

Invariant

The window [lo, hi] always contains at least one peak, because its boundary always sits below or at the element the search stepped from.

Why this is correct

Reasoning

Because neighbors are never equal and the ends are negative infinity, whenever nums[mid] < nums[mid+1] the right side must eventually stop rising and turn down, forming a peak; symmetrically the left retains one. So each step keeps a peak inside the window, and when lo meets hi that single element is it.

The algorithm in three movesSay these aloud before coding
1Set lo = 0 and hi = n - 1

lo=0 hi=3 mid=1 -> nums[1]=2 < nums[2]=3, lo=2

2Compare nums[mid] with nums[mid+1]

lo=2 hi=3 mid=2 -> nums[2]=3 > nums[3]=1, hi=2

3If it is smaller, move lo to mid + 1 (uphill right)

lo==hi=2 -> peak at 2

4Otherwise move hi to mid (peak is here or left)

5When lo == hi that index is a peak

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
21
32
13
1 · Readlo=0, hi=3
2 · AskDoes the slope rise at mid?
3 · Update statemid=1, nums[1]=2 < nums[2]=3
4 · ResultRising, so lo = 2
Key takeaway

Each step follows the rising side; the window collapses onto the peak at index 2.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3Initialize the window

    Search the whole array.

  2. 2
    Lines 4-5Loop while width remains

    Stop when lo == hi so mid+1 is always a valid index.

  3. 3
    Lines 6-9Follow the higher neighbor

    Rising slope goes right (lo = mid+1), otherwise keep mid on the left (hi = mid).

  4. 4
    Lines 10Return the peak

    The collapsed window points at a valid peak.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single element (it is trivially a peak)
  • Strictly increasing array (peak at last index)
  • Strictly decreasing array (peak at index 0)
  • Multiple peaks (any one is acceptable)
!

Common beginner mistakes

  • Using lo <= hi with hi = mid, which loops forever
  • Setting hi = mid - 1 and skipping a peak that sits exactly at mid
  • Accessing nums[mid+1] without the lo < hi guard, risking out of range
Check your understanding

Why is it safe to discard the entire left half when nums[mid] < nums[mid+1]?

More in Binary Search

#33Search in Rotated Sorted ArrayBinary search on a rotated array#153Find Minimum in Rotated Sorted ArrayBinary search for the rotation point#875Koko Eating BananasBinary search on the answer#4Median of Two Sorted ArraysBinary search on the partition#34Find First and Last Position of ElementLower-bound binary search on both ends#35Search Insert PositionLower-bound binary search