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

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

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time complexity.

Examples

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Example 3:

Input: nums = [1]
Output: 0
Explanation: For arrays with a single element, that element is a peak.

Constraints

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

Thinking Process

  1. Binary Search on Unsorted Array: Even though the array isn’t sorted, we can use binary search by comparing with neighbors
  • The search space must shrink monotonically each step.
  • Decide which half still satisfies the predicate, discard the other.
  • Use mid = left + (right - left) / 2 to avoid overflow.
Binary search: shrink [lo … hi] lo mid hi discard half each step → O(log n)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Standard binary search (this problem) O(log n) O(1) Sorted array, left <= right
Lower / upper bound O(log n) O(1) First/last position, insert index
Binary search on rotated array O(log n) O(1) Identify sorted half, discard other
Binary search on answer O(n log M) O(1) Monotonic predicate over search space

Solution

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
};

Solution Explanation

Approach: Standard binary search (this problem)

Key idea: 1. Binary Search on Unsorted Array: Even though the array isn’t sorted, we can use binary search by comparing with neighbors

How the code works:

  1. Binary Search on Unsorted Array: Even though the array isn’t sorted, we can use binary search by comparing with neighbors
    • The search space must shrink monotonically each step.
    • Decide which half still satisfies the predicate, discard the other.
    • Use mid = left + (right - left) / 2 to avoid overflow.

Walkthrough — input nums = [1,2,3,1], expected output 2:

3 is a peak element and your function should return the index number 2.

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  1. Binary Search on Unsorted Array: Even though the array isn’t sorted, we can use binary search by comparing with neighbors
  2. Peak Guarantee: The boundary conditions (nums[-1] = nums[n] = -∞) guarantee that a peak always exists
  3. Direction Choice: Comparing nums[mid] with nums[mid + 1] tells us which direction to search
  4. Loop Invariant: At each step, we maintain that a peak exists in the current search range [left, right]

References

Template Reference