75. Find Peak Element

做题历程：

1. 2016/Nov/05 原来在Leetcode中做过，本次耗时8分钟，独立解出

第一次做这道题的时候，我没有判断出这道题是用Binary Search，主要是本题的判断条件很不直接。。。

本题的判断条件是中间的元素与它左右两边对比：

• 如果比两边都大，这个值就能立即返回
• 如果呈上升趋势，应该丢掉左边
• 如果是下降去世，应该丢掉右边
• 如果中间的比两边都低，就随便找一边即可

代码如下：

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 = 1;
        int right = A.size() - 2;
        if (A.size() <= 2) {
            return -1;
        }

        while (left + 1 < right) {
            int middle = left + (right - left) / 2;
            if (A[middle] > A[middle-1] && A[middle] > A[middle+1]) {
                return middle;
            }
            else if (A[middle] > A[middle-1] && A[middle] < A[middle+1]) {
                left = middle;
            }
            else if (A[middle] < A[middle-1] && A[middle] > A[middle+1]) {
                right = middle;
            }
            else {
                left = middle;  // either way is OK
            }
        }
        return A[left] > A[right] ? left : right;
    }
};