Find Peak Element 寻找峰值

Find Peak Element 给定一个数组，其中任意两个相邻元素的值不等，寻找数组中某峰值的index i，使得n[i - 1] < n[i] > n[i + 1]。保证峰值一定存在，如果有多个峰值，可返回任意一个。

乍看此题不难，O(n)的算法很容易想到，直接遍历数组即可。但题目要求给出O(log(n))的算法。显然，直观上应该用二分查找，否则复杂度要求不能满足。可数组是无序的，无法直接应用二分查找。

开始的想法是分情况讨论n[m]与n[l]和n[r]的关系，但发现三者之间的关系与峰值是否存在联系不起来。这里就引入了第一个tricky的点：考虑n[m]与n[m - 1]的关系。

• n[m] > n[m - 1]: 峰值必出现在右边，l = m。反证法，若右边的数组单调递增，则最右的元素是峰值（这是第二个tricky的点，最初没想到单调递增的数组中也必存在峰值）；若右边的数组在某处开始递减，则峰值就在拐点。
• n[m] < n[m - 1]: 峰值必出现在左边，r = m - 1。同理可证。

算法有了，代码就有了？未尽然，还要考虑如下边界条件：

• 计算中点index int m = l + (r - l) / 2; 可能出现l=m的情况，处理不当导致死循环或下标越界。考虑到上述公式是倾向于选中点偏左的位置，那么使用n[m]与n[m+1]的关系可以让代码更简捷，在二分查找只剩下2个元素时，不会下标越界。
• 数组只有一个元素。在数组仅有一个元素时不必再计算中点，直接返回，因此循环停止条件为l < r而非l <= r。

综合上述分析，代码如下，非常简捷：

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

此题对二分查找的考察比较全面，对边界条件的处理要求较高，分析复杂，代码短小精干。