162. Find Peak Element

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 imagine that nums[-1] = nums[n] = -∞.

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

• new solution update 2022.02.23

c++

class Solution {
    int getOrDefault(vector<int>& nums, int i, int def = INT_MIN) {
        if(i < 0 or i >= nums.size())
            return def;
        return nums[i];
    }
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while(l < r) {
            int m = l + (r - l) / 2;
            int left = getOrDefault(nums, m - 1);
            int right = getOrDefault(nums, m + 1);
            if(nums[m] > left and nums[m] > right) return m;
            else if(left > right) r = m - 1;
            else l = m + 1;
            
        }
        return l;
    }
};

c++

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