Find Peak Element

A peak element is an element strictly greater than its neighbors. Given an array where nums[i] != nums[i+1], return the index of any peak.

Why this is worth learning

The array itself need not be monotone. Comparing a midpoint to its right neighbor gives a direction guaranteed to contain some peak, not necessarily the global maximum.

Before coding: one-minute experiment

For [1,4,2,3,1], may an implementation return either index 1 or index 3? Is a globally increasing array a special failure case?

Function signature

func FindPeakElement(nums []int) int

Inputs / outputs

• nums: array of integers.
• Return: an index of a peak element.

Example

nums = [1,2,3,1]
Output: 2  // nums[2] = 3 is a peak

Constraints

• 1 <= len(nums) <= 100_000
• nums[i] != nums[i+1]

Core idea (near-solution)

Scanning every position finds a peak in O(n). To discard half the positions, use a direction that certifies existence rather than compare against a target value. If nums[mid]<nums[mid+1], following that ascent must encounter either a descent or the outside right boundary, giving a peak. The proof also needs the retained interval’s outer slopes to point inward; a peak need not be the global maximum.

Use binary search on the slope. If nums[mid] < nums[mid+1], a peak must exist to the right; otherwise, a peak is at mid or to the left.

Invariant: there is always at least one peak in the current [lo, hi] range.

Algorithm (step-by-step)

1. Set lo = 0, hi = len(nums) - 1.
2. While lo < hi:
   • mid = lo + (hi-lo)/2.
   • If nums[mid] < nums[mid+1], set lo = mid + 1.
   • Else set hi = mid.
3. Return lo.

Correctness sketch

Treat positions outside the array as negative infinity. Maintain an interval that contains a peak, with boundary slopes pointing inward when needed. If nums[mid]<nums[mid+1], following the ascent to the right must eventually stop at a descent or the right boundary, yielding a peak there; discard through mid. Otherwise adjacent inequality makes nums[mid]>nums[mid+1], and an analogous argument finds a peak in the left portion including mid. Setting hi=mid retains that possible peak. The interval shrinks to one index whose neighbors are lower under the maintained boundary conditions.

Trace (hand walkthrough)

Example input:
nums = [1,2,3,1]
Output: 2  // nums[2] = 3 is a peak

Walk:
- lo=0, hi=3, mid=1: nums[1]=2 < nums[2]=3 -> lo=2
- mid=2: nums[2]=3 > nums[3]=1 -> peak at index 2

Pitfalls to avoid

• Accessing nums[mid+1] when mid is the last index (loop condition prevents this).
• Using linear scans when O(log n) is required.

Debugging lens

Validate the returned index against its existing neighbors, not one preferred answer. The loop lo<hi ensures mid+1 is inside the interval. Equal adjacent values are excluded by the contract.

Complexity

• Time: O(log n).
• Extra space: O(1).

Implementation notes (Go)

• The algorithm returns any valid peak, not necessarily the global maximum.

Reconstruction checkpoint

For [1,4,2,3,1], may an implementation return either index 1 or index 3? Is a globally increasing array a special failure case?

Return to Binary Search · Module quiz