Find Peak Element

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

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

Solution: Using Peak and Valley Approach

int findPeakElement(vector<int>& nums) {
    int peak = 0, valley = 0;

    int i = 1;
    while (i < nums.size()) {
        while (i < nums.size() && nums[i] > nums[peak]) {
            peak = i;
            i += 1;
        }
        return peak;            
    }
    return peak;
}

Solution: Binary Search

The key idea is to narrow down the

Note: The peak element is not equal to the largest element, it is the local maximum element

int findPeakElement(vector<int>& nums) {
    int low = 0;
    int high = nums.size()-1;

    while(low < high) {
        int mid1 = low + (high - low)/2;
        int mid2 = mid1+1;
        if (nums[mid1] < nums[mid2]) {
            low = mid2;
        } else {
            high = mid1;
        }
    }
    return low;
}