162. 寻找峰值

思路

这道题可以看到二分的本质，其实数组有序只是二分的一种可能条件，本质上二分要求的是原问题可以二分为更小规模的子问题，或者说是“二段性“，舍去另一半规模的问题，仍然可以求出原问题的解。

在本题中，如果我们找到的区间中点的元素，其右边的元素值小于它，那么这个元素就可能是问题的一个解，我们以这个元素作为新的右边界，否则我们选择右边元素作为左边界。实际上，以为nums[-1]和nums[n]都为负无穷，这个新的右（左）边界也满足了上述性质，问题转为了更小规模的子问题。

而显然，当问题减小到只有1的规模，这个点就是一个满足要求的峰值点，因此我们不会因为二分区间而找不到峰值点，这个解法是可行的。

代码

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        int l = 0;
        int r = n - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (mid < n - 1 && nums[mid] > nums[mid + 1]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }
}