# 162 - Find Peak Element

解法一 - Divide nad Conquer

這題可以用 D&C 來想想看，如果我們把 nums 切成左右兩半，我們可以看看當時的 mid 是不是比左右兩邊鄰居都大，如果是的話，那就直接回傳，不然就是要比較左右兩邊哪個比較大。

不過每次都分成兩個子問題，子問題大小是原本的 1/2，那這樣就變成 O(n) 的時間複雜度，不符合題目要求。

另外下面的實作只能通過 Leetcode 上 57/59 的例子，但這是我頭幾次自己寫出 D&C 的程式碼，還是滿有成就感的，記錄一下ＸＤ

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int res, maxVal;

        maxVal = helper(nums, 0, nums.size()-1, res);

        return res;
    }

private:
    int helper(const vector<int>& nums, int start, int end, int& index) {
        int mid = start + (end-start)/2;
        int maxVal;

        if(mid == start) {
            if(nums[mid] > nums[end]) {
                index = mid;
                maxVal = nums[mid];
                return maxVal;
            }
            else {
                index = end;
                maxVal = nums[end];
                return maxVal;
            }
        }
        if(mid == end) {
            if(nums[mid] > nums[start]) {
                index = mid;
                maxVal = nums[mid];
                return maxVal;
            }
            else {
                index = start;
                maxVal = nums[start];
                return maxVal;
            }
        }

        if(nums[mid-1] < nums[mid] && nums[mid] > nums[mid+1]) {
            index = mid;
            maxVal = nums[mid];
            return maxVal;
        }
        else {
            int leftInd, rightInd;
            int leftMax  = helper(nums, start, mid, leftInd);
            int rightMax = helper(nums, mid+1, end, rightInd);

            if(leftMax > rightMax) {
                index = leftInd;
                maxVal = leftMax;
                return maxVal;
            }
            else if(leftMax < rightMax) {
                index = rightInd;
                maxVal = rightMax;
                return maxVal;
            }
        }

        return maxVal;
    }

};

解法二 - binary search

如果我們每次都找 mid，會看到幾種情況：

1. mid 處在往下的坡：那就往左邊搜尋 peak

2. mid 處在往上的坡：那就往右邊搜尋 peak

3. mid 處在山峰：那就回傳 mid

4. mid 處在山谷：那就往兩邊都可以

實作出來的程式碼如下：

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int start=0, mid, end=nums.size()-1;
        int res = -1;

        while(start+1 < end) {
            mid = start + (end-start)/2;

            if(nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1]) {
                res = mid;
                break;
            }
            else if(nums[mid] > nums[mid+1]) {// there's a peak on the left
                end = mid;
            }
            else {// there's a peak on the left
                start = mid+1;
            }
        }

        if(res == -1 && nums[start]>nums[end]) res = start;
        if(res == -1 && nums[start]<nums[end]) res = end;
        if(res == -1) res = start;

        return res;
    }
};