【leetcode】寻找峰值 [m]（二分）-爱代码爱编程
一、题目
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 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]
二、代码
class Solution {
public int findPeakElement(int[] nums) {
int n = nums.length;
// 数组长度为1，直接返回0下标
if (n == 1) {
return 0;
}
// 先判断两个特殊情况，也就是数组两头的数是不是局部最小，如果是的话直接返回。反正题目只要求返回一个符合局部最小的数即可
if (nums[0] > nums[1]) {
return 0;
}
if (nums[n - 1] > nums[n - 2]) {
return n - 1;
}
// 执行到这里，左右两端的数一定都小于相邻的数
// 设置数组的左右范围
int l = 0;
int r = n - 1;
// L...R 肯定有局部最大。
// 最左端的数比相邻的数小，最右端的数比相邻的数小，因为相邻的数没有相等的，他们在坐标系上的线是一个向下凹的弧度，所在在中间必然有一个值既大于左边相邻的数，也大于右边相邻的数。
// 开始通过二分法进行查找
while (l < r - 1) { // 这里用的是L < R - 1，之所以用R - 1是因为怕越界，因为要想判断mid,mid-1,mid+1就要保证这三个位置都在L~R的范围里面，所以这里就要让L < R - 1。
// 设置中间下标
int mid = (l + r) >> 1;
// 如果找到了符合局部最大的数，直接返回其下标
if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
return mid;
} else {
// 如果中间位置的数小于其左侧相邻的数，说明mid-1的数至少是大于mid的，所以保留mid-1，去左半段继续查找，更新R的值即可
// 我们要找凸线的最高点，此时mid-1位置比mid的更高，自然要去左侧找凸线的最高点
if (nums[mid] < nums[mid - 1]) {
r = mid - 1;
// 反之，说明mid+1的数是大于等于mid的，所以保留mid+1，去右半段继续查找，更新L的值即可
} else {
l = mid + 1;
}
}
}
// 如果跳出循环还没有找到局部最大，说明当前L~R范围的数只有2个或者1个，这样我们就直接判断这两个数谁比较大就返回谁。因为L位置一定比左侧的数大，R位置一定比右侧的大，只要是比较出L和R谁大，就能知道谁是局部最大了
// 如何L = R，说明范围内只有一个数，直接将其返回即可
return nums[l] > nums[r] ? l : r;
}
}三、解题思路
先去判断数组两端的两个数是不是满足局部最大，如果满足了直接返回下标即可。如果不满足，再去进行后续的流程。
进行后面的流程，一定能保证左右两端的数都比其相邻的数小，所以左右两端的斜率都是向上的，然后整个坐标系连线一定是连在一起的，那就说明一定会在坐标系的中间某个位置再连在一起，一开始左右两端斜率都向上，所以中间必然存在一个位置斜率为0，让左右的线连接在一起，而这个位置也就比左右都小。所以在坐标系看就是一个凸形的线。所以中间必然有一点即比左边的数大，又比右边的数大。
任意两个都相邻是不相等的，所以中间必然存在一个变化曲线，先往上扬，后是下降，中间我不管你怎么连这个变化曲线一定存在局部最大。