162. Find Peak Element

1. Description

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.

2. Example

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.

3. Constraints

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

4. Solutions

Binary Search

n = nums.size()
Time complexity: O(logn)
Space complexity: O(1)

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

            // We only need to find any peak, so we move toward a direction that must contain one.
            if (middle > 0 && nums[middle] > nums[middle - 1]) {
                left = middle + 1;
            } else {
                right = middle;
            }
        }

        return left;
    }
};