# Find Peak Element

## Description

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

Given an input array `nums`, where `nums[i] ≠ nums[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 `nums[-1] = nums[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: 1 or 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.
```

**Note:**

Your solution should be in logarithmic complexity.

## Solution

Proof:

1. Loop invariant: `nums[l-1] < nums[l]` and `nums[r] > nums[r+1]` and the peak's index is in `[l, r]`.
2. `mid + 1` $$\le$$ `r`.
3. If `nums[mid] < nums[mid + 1]`,
   1. If `nums[mid+1], ..., nums[r]` is monotonically increasing, `nums[r]` is the peak element.
   2. Otherwise, there must be an index `i` in `[mid+1, r-1]` such that `nums[i] > max(nums[i-1], nums[i+1])`. `nums[i]` is the peak element.
   3. So the peak index is in `[mid+1, r]`.
4. Otherwise, the peak index is in `[l, mid]`. The proof is similar.

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