Find Peak Element

Explanation & Solution

Description

A peak element is an element that is strictly greater than its neighbors.

Given an integer array nums, find a peak element and return its index. If the array contains multiple peaks, return the index to any of them.

You may imagine that nums[-1] = nums[n] = -∞. You must write an algorithm that runs in O(log n) time.

Input:nums = [1, 2, 3, 1]

Output: 2

Explanation: 3 is a peak element and index 2 is returned.

Constraints

1 <= nums.length <= 1000
-2^31 <= nums[i] <= 2^31 - 1
nums[i] !== nums[i + 1] for all valid i

Approach

Modified Binary Search pattern

1. Initialize Pointers

Set left = 0 and right = nums.length - 1.

2. Binary Search for Peak

Compute mid = (left + right) >> 1.
Compare nums[mid] with nums[mid + 1].

3. Follow the Ascending Slope

If nums[mid] < nums[mid + 1], we're on an ascending slope → a peak must exist to the right. Set left = mid + 1.
Otherwise, we're on a descending slope → a peak is at mid or to the left. Set right = mid.

4. Return the Peak Index

When left === right, we've converged on a peak. Return left.

🧠 Key Insight

Since nums[-1] = nums[n] = -∞, if we always move toward the higher neighbor, we are guaranteed to find a peak. No two adjacent elements are equal, so there's always a clear direction.

Time

O(log n)binary search halves the space each time.

Space

O(1).

Visualization

Input:

[1, 2, 3, 1]

—

Press ▶ or use ← → to step through

Left (L)Right (R)ConvergedDone

7 steps

Solution Code

Find Minimum in Rotated Sorted Array

First Bad Version