Find Peak Element

Find Peak Element.png

===================== 解題思路 =====================

二分法直到找出 A[mid] > A[mid - 1] && A[mid] > A[mid + 1] 為止
如果找到的點比前一個點小 (A[mid] < A[mid -1]) 說明可能的 peak 在左邊 所以設定 right = mid 來往左邊找 反之則是設定 left = mid 往右邊找

===================== C++ code ====================

<pre><code>
class Solution {

public:

/**
 * @param A: An integers array.
 * @return: return any of peek positions.
 */
int findPeak(vector<int> A) {
    // write your code here
    int left = 0, right = A.size() - 1;
    while(left + 1 < right)
    {
        int mid = left + (right - left) / 2;
        if(mid > 0 && A[mid] > A[mid - 1] && A[mid] > A[mid + 1]) return mid;
        if(A[mid] < A[mid -1]) right = mid;
        else left = mid;
    }
    if(A[left] > A[right]) return left;
    else return right;
}

};
<code><pre>