今天是我坚持写题解的第 42 天！

题目描述（Medium）

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：

输入：nums = [1,2,3,1] 

输出：2

解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

输入：nums = [1,2,1,3,5,6,4] 

输出：1 或 5

解释：你的函数可以返回索引 1，其峰值元素为 2；或者返回索引 5， 其峰值元素为 6。

提示：

1 <= nums.length <= 1000
-2^31 <= nums[i] <= 2^31 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]

链接：https://leetcode-cn.com/problems/find-peak-element

方法、二分查找

首先，先来理解题目的含义，题目让我们找到给定数组中的峰值的下标，那么，什么是峰值呢？

例如，以 nums = [1,2,1,3,5,6,4] 为例，如下图，峰值就是某个数两边相邻的数都比它小的数，明显，2 和 6 是这个数组的两个峰值，它们对应的下标分别是 1 和 5，所以返回 1 和 5 中的任意一个就可以了。

然后，题目要求了，必须实现时间复杂度为 的算法，这是很强烈的二分暗示。

那么，怎么使用二分呢？

我们观察峰值的特性，可以得出，对于下标 i ，如果满足 nums[i-1] < nums[i] > nums[i+1] ，那么，nums[i] 就是峰值，所以，我们可以使用二分先找到中间的位置，如果 nums[mid] > nums[mid+1] ，那么，峰值肯定在 mid 或者它左边的位置，因为，我比我右边的元素大，但是我不一定比我左边的元素大，所以，要往左边找，看有没有比我还大的数，直到左右指针相遇，相遇的位置就是我们要找的峰值。

当然，本题是基于假设 对于所有有效的 i 都有 nums[i] != nums[i + 1] ，即相邻的元素不相等，如果相邻的元素可以相等，就不能使用二分查找了。

好了，请看代码，直接套用二分模板即可：

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }
}

• 时间复杂度： 。
• 空间复杂度： 。

运行结果如下：

最后

如果对你有帮助，请点个赞吧，谢谢^^

也可以关注我，每日分享题解，一起刷题，一起拿全家桶。