[162] 寻找峰值

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

给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[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。

说明:

你的解法应该是 O(logN) 时间复杂度的。

这题最简单的当然是一个复杂度为O(n)的解法，不断比较当前值与后一个值的大小，直到后一个值比当前值大，则当前位置一定为一个峰值点。

 var findPeakElement = function(nums) {
   for (let i = 0; i < nums.length; i++) {
     if (nums[i] > nums[i + 1]) return i;
   }
   // 单调递增时，即最后一个值最大
   return nums.length - 1;
 };

但是如果题目要求时间复杂度为O(lgn)的话，就只能从二分的角度下手了。

算法思路的关键在于，对于任意一点与其相邻的节点，沿着递增一侧的方向一定能够找到一个峰值。如比较mid与mid+1位置上值的大小，如果mid值较大，则[left, mid)一定有峰值，反之[mid+1, right)一定有峰值。

function findPeakElement(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] > nums[mid + 1]) {
      // 说明此时一定在mid左侧有峰值，缩小右边界范围
      right = mid;
    } else {
      // 说明此时一定在mid右侧有峰值，缩小右边界范围
      left = mid + 1;
    }
  }
  return left;
}