C++ 面试高频考点 力扣 162. 寻找峰值 二分查找 题解 每日一题

题目描述

题目链接：
力扣162. 寻找峰值

题目描述：

示例 1:
输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，其左右相邻元素都小于它。

示例 2:
输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5
解释: 数组有两个峰值：2（下标1）和6（下标5），返回任意一个即可。

注意：
1 <= nums.length <= 1000
-2^31 <= nums[i] <= 2^31 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]（数组元素严格递增或递减，无相等情况）

为什么这道题值得弄懂？

这道题是 山脉数组峰顶索引 的进阶延伸，核心同样是利用二分查找的「二段性」，但在场景上更灵活：

• 不再限制数组是“严格递增后严格递减”的单一山脉，而是允许存在多个峰值；
• 引入了“边界视为负无穷”的规则，让数组两端也可能成为峰值（如 nums = [2,1] 中，下标0是峰值；nums = [1,2] 中，下标1是峰值）。

通过这道题，能进一步打破对“二分查找仅适用于完全有序数组”的刻板认知，掌握“如何根据自定义规则（如边界假设、局部单调性）构建二分判断条件”，同时强化对“指针移动逻辑”“边界初始化”的灵活运用能力，是理解二分查找本质的关键题目。

为什么可以用二分？

二分查找的核心是“通过一个判断条件，将数组划分为‘满足条件’和‘不满足条件’的两段，每次舍弃一段，缩小查找范围”。本题的关键在于，即使数组存在多个峰值，依然能通过「局部单调性」定义这样的“二段性”：

基于题目中“nums[-1] = nums[n] = -∞”和“nums[i] != nums[i+1]”的规则，对于任意下标 mid，必然存在以下两种情况之一：

1. 若 nums[mid] < nums[mid + 1]：说明从 mid 到 mid+1 是严格递增的。由于右侧边界是负无穷，沿着递增方向必然会遇到一个“由增转减”的点（即峰值），因此峰值一定在 mid 的右侧（包括 mid+1）；
2. 若 nums[mid] > nums[mid + 1]：说明从 mid 到 mid+1 是严格递减的。由于左侧边界是负无穷，沿着递减方向必然会遇到一个“由减转增”的点（即峰值），因此峰值一定在 mid 的左侧（包括 mid）。

基于此特性，我们可通过二分不断缩小区间，最终定位到任意一个峰值的下标。

二分查找的核心思路：基于“局部增减性”缩小区间

本题的核心是通过 nums[mid] 与 nums[mid + 1] 的大小关系，判断当前位置的局部增减趋势，进而确定峰值的可能范围，逐步缩小查找区间。

1. 关键细节：边界初始化（为什么 left=0，right=nums.size()-1？）
与「山脉数组峰顶索引」不同，本题有两个关键差异决定了边界初始化方式：

• 峰值可能出现在数组两端（如 nums = [1,2] 中，下标1是峰值；nums = [2,1] 中，下标0是峰值）；
• 数组长度可能为1（此时唯一元素就是峰值）。

因此，初始边界必须覆盖整个数组：

• left = 0：包含数组第一个元素（可能是峰值）；
• right = nums.size() - 1：包含数组最后一个元素（可能是峰值）。

同时，这种初始化不会导致 mid+1 越界：因为循环条件是 left < right，当 right = nums.size()-1 时，mid 最大为 nums.size()-2（向下取整），mid+1 最大为 nums.size()-1，属于合法下标。

2. 二段性划分与判断条件
以 nums[mid] < nums[mid + 1] 作为核心判断条件，将数组划分为两段：

• 满足条件（局部递增）：nums[mid] < nums[mid + 1] → 峰值在 mid 右侧（mid + 1 到 right）；
• 不满足条件（局部递减）：nums[mid] > nums[mid + 1] → 峰值在 mid 左侧（left 到 mid）。

示例1：若 nums = [1,2,3,1]，初始 left=0, right=3：

• 第一次计算 mid = 0 + (3-0)/2 = 1，nums[1]=2 < nums[2]=3 → 峰值在右侧，left = 1+1=2；
• 此时 left=2 < right=3，计算 mid = 2 + (3-2)/2 = 2，nums[2]=3 > nums[3]=1 → 峰值在左侧，right=2；
• 循环结束，left==right=2，即为峰值下标（正确）。

示例2：若 nums = [1,2,1,3,5,6,4]，初始 left=0, right=6：

• 第一次 mid=3，nums[3]=3 < nums[4]=5 → left=4；
• 第二次 mid=4 + (6-4)/2 = 5，nums[5]=6 > nums[6]=4 → right=5；
• 循环结束，left==right=5，即为峰值下标（正确，6是峰值）。

3. 指针移动逻辑
根据上述二段性划分，指针移动规则与「山脉数组」一致，但背后的逻辑更通用：

• 当 nums[mid] < nums[mid + 1] 时：局部递增，峰值在右侧，舍弃左侧区间（包括 mid），将 left 更新为 mid + 1；
• 当 nums[mid] > nums[mid + 1] 时：局部递减，峰值在左侧（或 mid 本身），舍弃右侧区间（不包括 mid），将 right 更新为 mid。

关键逻辑：为什么 nums[mid] > nums[mid + 1] 时 right = mid？
因为 mid 有可能就是峰值（例如 nums = [3,2,1]，mid=0 时 nums[0] > nums[1]，mid 本身就是峰值），若将 right 更新为 mid - 1，会漏掉这个峰值，导致结果错误。

4. 循环结束条件
循环条件设为 left < right：当 left == right 时，区间缩小到唯一元素，该元素就是一个峰值（由二分的二段性保证），循环结束。

无需额外验证的原因：每一步二分都严格根据“局部增减性”向峰值方向缩小范围，最终 left 和 right 收敛的元素，必然满足“严格大于左右相邻元素”（或处于边界，边界外视为负无穷），因此一定是峰值。

5. 中间值（mid）的取法
采用向下取整：mid = left + (right - left) / 2（等价于 (left + right) // 2，避免整数溢出）。

为什么不能用向上取整？
若用向上取整（mid = left + (right - left + 1) / 2），当区间长度为2时（如 left=0, right=1，nums = [1,2]）：

• 计算 mid = 0 + (1-0+1)/2 = 1；
• 判断 nums[1] > nums[2]（nums[2] 不存在，实际 mid=1 是 right 边界，nums[1] 右侧是负无穷，满足 nums[1] > 负无穷），则 right=1；
• 此时 left=0 < right=1，循环继续，再次计算 mid=1，陷入死循环。

而向下取整可避免此问题：

• 同样 left=0, right=1，mid=0 + (1-0)/2 = 0；
• 判断 nums[0] < nums[1]，则 left=0+1=1，此时 left==right，循环结束，返回1（正确）。

代码实现

class Solution {
public:int findPeakElement(vector<int>& nums) {// 边界初始化：覆盖整个数组（峰值可能在两端或唯一元素）int left = 0, right = nums.size() - 1;// 循环缩小区间，直到left == right（定位到任意一个峰值）while (left < right) {// 中间值向下取整，避免区间长度为2时的死循环int mid = left + (right - left) / 2;if (nums[mid] < nums[mid + 1]) {// 局部递增，峰值在右侧，舍弃左侧left = mid + 1;} else {// 局部递减，峰值在左侧（含mid），舍弃右侧right = mid;}}// 循环结束时，left == right，即为峰值下标return left;}
};

总结

为了更清晰地理解两道题的差异与联系，我们通过表格对比关键细节：

对比维度	力扣162. 寻找峰值	力扣852. 山脉数组的峰顶索引
峰值数量	可能有多个，返回任意一个即可	只有一个，返回唯一峰值
峰值位置限制	可在数组两端（或唯一元素）	不可在两端（0 < 峰值下标 < n-1）
初始边界	left=0，right=n-1（覆盖整个数组）	left=1，right=n-2（排除两端）
核心判断条件	nums[mid] < nums[mid+1]（局部增减性）	nums[mid] < nums[mid+1]（递增/递减段）
指针移动逻辑	完全一致（left=mid+1 / right=mid）	完全一致
中间值取法	向下取整（避免死循环）	向下取整（避免死循环）

核心复盘

1. 边界初始化要匹配题目规则：本题因“峰值可在两端”，需覆盖整个数组；山脉数组因“峰值不可在两端”，可排除首尾，减少查找次数。边界设计的核心是“不遗漏可能的目标范围”。
2. 判断条件的本质是“二段性”：无论数组是单一山脉还是多峰值，只要能通过一个条件将数组划分为“有目标”和“无目标”的两段，就能用二分。本题的“二段性”来自“局部增减性+边界负无穷”的组合假设。
3. 指针移动避免“漏解”：只要目标可能在 mid 处（如本题中 nums[mid] > nums[mid+1] 时，mid 可能是峰值），就必须将 right 设为 mid，而非 mid-1，否则会漏掉目标。
4. 中间值取整匹配循环逻辑：当 left 可能更新为 mid+1、right 可能更新为 mid 时，必须用向下取整，否则会在区间长度为2时陷入死循环。

结尾 + 下一篇题目预告

如果你是那位时常挂念我的博客、几乎从未错过更新的老朋友，那么现在面对这些二分查找题目，想必会觉得得心应手。就像我在第一篇二分专题博客里提到的那样：二分查找这东西，懂了就一点不难，没吃透就会很难，核心的难点往往藏在细节里。一旦你真正吃透了二分的底层逻辑，能精准把控边界条件这些关键细节，后续的题目其实都是在基础模板上，根据题干要求来做调整、增减条件。遇到经典的二分基础题可以瞬秒。

当然，第一次看我的博客的朋友也绝对没问题你现在缺的或许只是系统的总结和针对性练习。既然能读到这里，就足以说明你对算法满怀热情，并且正主动深入探索二分查找——这份求知欲已经让你走在了很多人前面。

如果你想从最基础的内容开始梳理，可以先从力扣 704.二分查找 基础二分查找这篇开始，每天抽点时间看一篇。相信这段时间的二分专题系列内容，能帮你拨开思路里的迷雾，彻底搞懂二分查找。

如果觉得这些内容对你有帮助，不妨点个赞支持一下，再关注我的博客。后续我还会持续分享更多算法干货，跟着系列文章一步步学，你对二分查找的掌握一定会越来越扎实～

本次我们通过“寻找峰值”掌握了“灵活定义二段性+边界假设”的二分思路，下一篇将挑战更复杂的二分变形题——153. 寻找旋转排序数组中的最小值。