# 2.寻找峰值（middle）

TIP

更好的阅读体验应该是：

  1. 审题-思考
  2. 答题
  3. 整理-归纳

# 一、题目

LeetCode：162.寻找峰值 (opens new window)

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

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

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

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

输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5
解释: 你的函数可以返回索引 1，其峰值元素为 2；或者返回索引 5， 其峰值元素为 6。

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

# 二、基础模版 II

  1. 确定初始的左右边界:
    • left: 0
    • right: nums.length-1
    • mid: (left + (right - left) >> 1)
  2. 查找条件需要访问元素的直接右邻居。
  3. 使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
  4. 保证查找空间在每一步中至少有 2 个元素。
  5. 需要进行后处理。 当你剩下 1 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。

# 三、题解

分析模版

  • 我们的目标是：寻找一段顺序区间内最大的元素
  • 我们拥有的访问区间不是顺序的，我们需要自己划分

Javasciprt 代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var findPeakElement = function(nums) {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    let mid = left + ((right - left) >> 1);
    // 这里需要保证区间内有2个元素
    if (nums[mid] < nums[mid + 1]) {
      // 这证明 mid + 1 更有可能是当前区间的峰值，并且左侧是递减区间，可以抛弃
      left = mid + 1; //
    } else {
      // 这证明 mid 更有可能是当前区间的峰值，并且右侧是递减区间，可以抛弃，但注意保留mid
      right = mid;
    }
  }
  return left;
};

# 四、写在最后

本文是二分查找-模版 II 的第二题，你可能意识到了，相对应的 leetcode 给他们标出中等的难度，加油！

如果对你有所帮助不妨给本项目的github 点个 star (opens new window)，这是对我最大的鼓励～

关于我

  • 花名：余光
  • WX：j565017805
  • 沉迷 JS，水平有限，虚心学习中

其他沉淀

Last Updated: 8/6/2021, 6:58:15 PM