1. 写在前面
本文为个人学习总结，参考：B站Up：灵茶山艾府
参考视频链接：https://www.bilibili.com/video/BV1QK411d76w/
2. 题目
我们来看一下下面这道题：
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 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。
3. 解法
这有什么难的？遍历！嘿嘿，遍历的时间复杂度为O(n)，题目要求时间复杂度为 O(log n)，很经典的二分查找的时间复杂度。但是数组并不是有序呀，还能用二分吗？
其实，二分查找的应用并不限制要求数组一定有序，只需要我们求解的目标满足二段性即可。我们在二分查找的时候，每次都会筛选掉一半的内容，而我们只要能找到一个分割点，将目标数组分割为两段内容，我们就可以运用二分的思想解决问题。
峰值元素，指的是比相邻左边和相邻右边都大的元素，在数学层面我们可以理解为局部极大值。我们可以将寻找峰值元素的过程比喻成爬山，对于数组中的每一个元素，无非就三种状态：在上山，在峰顶，在下山，如果我们一直往高处走，我们可能会继续上山，或者到达峰顶；如果我们往低处走，我们是没有办法到达峰值元素的。也就是说，峰值一定会在值大的一侧，在我们寻找峰顶的过程中，我们都是尽量地往值大的方向去寻找峰顶。
当我们比较nums[mid]和nums[mid+1]的关系后，我们就可以确定峰值会出现在哪一边了。
我们可以看个图帮助理解一下：
你可能会问：为什么一直往高处走肯定会到达峰顶呢？或者是，为什么峰值一定会在值大的一侧？我们需要注意到，题目中存在一个最最最最重要的前提：
假设 nums[-1] = nums[n] = -∞ 。
也就是说，我们最坏的情况无非就是一直往高处走停不下来，直到走到数组末尾，假如数组为[1，2，3，4]，其实它是：[-∞，1，2，3，4，-∞]，在这种情况下，4比左右两边都要大，4就是峰顶。
那么，我们是不是已经找到了二分法的分割点了呀。我们运用红蓝染色法，首先确定循环不变量，也就是红色区域和蓝色区域分别代表什么。我们规定：
红色（左边部分）：峰顶左侧的元素
蓝色（右边部分）：峰顶或者峰顶右侧的元素
定义左指针 L = 0， 右指针R = nums.length - 2，左指针左侧区域为红色，右指针右侧区域为蓝色。
为啥右指针R不指向nums的最后一位（R = nums.length - 1），因为数组的最后一位元素要么是峰顶，要么是峰顶右侧的元素，肯定为蓝色，所以可以从倒数第二位开始判断。
题目中还有一个前提：
对于所有有效的 i 都有 nums[i] != nums[i + 1]
也就是说相邻元素肯定不相等，我们每次比较 nums[mid] 和 nums[mid+1] 的关系，如果：
① nums[mid] < nums[mid+1]
右侧大，右侧肯定有峰值，我们移动 L 左指针至 mid+1 位置
② nums[mid] > nums[mid+1]
左侧大，左侧肯定有峰值，我们移动 R 右指针至 mid-1 位置
当二分查找结束，退出循环时，左指针 L 指向结果， 或者右指针的右一位 R+1 指向结果，返回哪个都行。
4. 代码（Java版本）
class Solution {
public int findPeakElement(int[] nums) {
int left = 0;
int right = nums.length - 2;
while(left<=right){
int mid = (left + right) /2;
if(nums[mid]<nums[mid+1]){
left = mid + 1;
}
else{
right = mid - 1;
}
}
return left;
}
}