Find Peak Element medium

Problem Statement

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 the peaks.

You may assume that nums[-1] = nums[n] = -∞.

Constraints:

• 1 <= nums.length <= 1000
• -2³¹ <= nums[i] <= 2³¹ - 1
• You must write an algorithm that has a time complexity of O(log n).

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: 6 is a peak element and your function should return the index number 5.

Steps

1. Binary Search: We can solve this problem efficiently using binary search. The key insight is that if nums[mid] < nums[mid + 1], then a peak must exist in the right half (because the array slopes upward at mid). Conversely, if nums[mid] < nums[mid - 1], a peak must exist in the left half.

2. Base Cases: We need to handle the base cases where the array has only one element (which is always a peak) or two elements.

3. Iteration: The binary search iteratively narrows down the search space until a peak is found.

Explanation

The algorithm leverages the property that a peak element must exist. The binary search efficiently explores the array, eliminating half of the search space in each iteration. By comparing the middle element with its neighbors, we determine which half of the array contains a peak. This process continues until a peak is located. The -∞ assumption simplifies boundary conditions.

Code

#include <vector>

class Solution {
public:
    int findPeakElement(const std::vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;

        while (left < right) {
            int mid = left + (right - left) / 2; // Avoid integer overflow

            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1; // Peak is in the right half
            } else {
                right = mid; // Peak is in the left half (including mid)
            }
        }
        return left; // left == right, so either is the index of the peak
    }
};

Complexity

• Time Complexity: O(log n) due to the binary search.
• Space Complexity: O(1) as the algorithm uses a constant amount of extra space.