# [LeetCode 162. Find Peak Element](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/609/week-2-july-8th-july-14th/3812/)
### Daily challenge Jul 13, 2021 (MEDIAN)

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

:::info
**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.
:::

:::info
**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.
:::

:::warning
**Constraints:**
* 1 <= nums.length <= 1000
* -231 <= nums[i] <= 231 - 1
* nums[i] != nums[i + 1] for all valid i
:::

---

### Approach 1 : Brute Force :bulb:
**`4 ms`**

從 **`i = 1`** 的位置開始遍歷所有元素。
當找到一個元素 `nums[i]` 符合 **`nums[i] > nums[i-1] && nums[i] > nums[i+1]`**，就表示 `nums[i]` 為 Peak Element。

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int size = nums.size();
        
        if(size == 1)   return 0;
        if(nums[0] > nums[1])   return 0;
        if(nums[size-1] > nums[size-2]) return size-1;
        
        for(int i=1; i<nums.size()-1; i++){
            if(nums[i] > nums[i-1] && nums[i] > nums[i+1])  return i;
        }
            
        return -1;
    }
};

### Approach 2 : Brute Force ( more clean ) :bulb:
**`4 ms`**

因為 **`nums[-1] = nums[n] = -∞`** 且我們可以回傳**任意** peaks，所以我們**不必**確認 **`nums[i] < nums[i-1]`**，只需從 **`i = 0 ~ nums.end()-1`** 開始判斷 **`nums[i] > nums[i+1]`**。

若迴圈中沒有找到答案，則表示**最後一個元素**就是 Peak Element。

>**Input:** nums = [1,2,3]
>i = 0 ---> 1 < 2 :x:
>i = 1 ---> 2 < 3 :x:
>end loop
>3 is a peak element

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int size = nums.size();
        
        for(int i=0; i<size-1; i++){
            if(nums[i] > nums[i+1]){
                return i;
            }
        }
        return size-1;
    }
};

### Approach 3 : binary search :book:
`0 ms`

:::warning
Why can we use binary search on unsorted array ?
:::

>**case1:** nums[middle] > nums[middle+1], means peak is on the *left side*.
>**case2:** left == right
>**case3:** nums[middle] < nums[middle+1], means peak is on the *right side*.

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        // binary search (didn't need sort, only for this question)
        int left = 0;
        int right = nums.size() - 1;
        
        while(left < right){            
            int middle = (left + right) / 2;
            if(nums[middle] > nums[middle+1])   right = middle;
            else    left = middle + 1;
        }
        
        return left;
    }
};