LeetCode 162：寻找峰值（二分查找） —— 题解
👋 欢迎阅读
🎯 欢迎来到「寻找峰值」题解之旅！本文将带你从"在连绵起伏的山峦中任选一座山顶"这一直观场景出发，深入理解二段性二分的巧妙运用，并掌握如何比较相邻元素判断坡向来定位任意一个峰值下标。
在开始之前，建议你先：
了解题目背景：这是 LeetCode 162 题，给定数组
nums，相邻元素不相等，峰值定义为严格大于左右邻居的元素（边界只需大于一侧邻居），返回任意一个峰值下标。本质上，数组必然存在峰值，且二段性——左侧可能上升、右侧可能下降，问题转化为二分收敛到任一分界点。明确学习目标：掌握比较 nums[mid-1] 与 nums[mid] 的上取整模板，理解与 852 题的镜像对称关系，并熟练处理单元素、双元素与峰在边界等边界情况。
准备好环境：建议在本地 IDE 或 LeetCode 在线编辑器中打开代码，边看边运行，亲手验证示例（如
nums = [1,2,3,1]输出2，nums = [1,2,1,3,5,6,4]输出5或1）。
本文将从问题转化、坡向判断、区间收缩、返回结果到代码实现，层层递进。即使你对二段性二分还不熟悉，我们也会从"往坡上走，总能到山顶"这一直觉出发，让你轻松抓住核心思想——看坡向，往高处走，必达峰顶。现在，让我们一起二分爬山，找到任一座峰顶吧！ ⛰️🎯
一.题目
162. 寻找峰值 - 力扣（LeetCode）
二.做题思路
一、问题分析（前置分析）
- 题目要求：在任意数组（相邻元素不相等）中返回任意一个峰值下标（
nums[i] > nums[i-1]且nums[i] > nums[i+1]，边界元素只需大于其唯一邻居）。 - 关键约束：峰值必然存在（全局最大值必是峰值）；返回任意一个即可；相邻元素不相等。
- 核心思路：利用二段性与"往上升方向走必达峰顶"的性质，用二分在 O(log n) 内收敛到任一个峰值。
二、算法策略（二段性二分 · 前邻比较）
核心步骤：
- 初始化区间：
left = 0、right = n - 1。 - 二分收敛：
while (left < right)，mid上取整（left + (right - left + 1) / 2），保证mid >= 1使nums[mid-1]安全。 - 前邻比较：
nums[mid - 1] > nums[mid]→ 从mid-1到mid是下降，峰值在左半，right = mid - 1；nums[mid - 1] < nums[mid]→ 从mid-1到mid是上升，峰值在右半（含 mid），left = mid。
- 返回：循环结束后
left == right即任一个峰值下标。
示例执行过程（nums = [1,2,3,1]）：
| 阶段 | left | right | mid | nums[mid-1] vs nums[mid] | 操作 | 结果 |
|---|---|---|---|---|---|---|
| ① | 0 | 3 | 2 | 2 < 3 | 上升，收缩左侧 | left=2 |
| ② | 2 | 3 | 3 | 3 > 1 | 下降，收缩右侧 | right=2 |
| 收敛 | 2 | 2 | — | — | 返回 2 | 2 |
三、正确性说明（简单版本）
- 峰值必然存在：全局最大值一定满足峰值定义（或边界峰值），所以必有解，无需处理无解分支。
- 坡向判据可靠：
nums[mid-1] > nums[mid]说明 mid 在下降段，其左侧必有一个峰值（沿上升方向回溯）；反之在上升段，右侧必有一个峰值。判据不会漏掉可行方向。 - 收缩方向正确：下降段丢弃右半（含 mid），上升段保留 mid 向右收敛，区间单调缩小且始终含至少一个峰值，不会漏解。
- 终止性：
right = mid - 1与left = mid（上取整保证mid > left）均严格缩小，不会死循环。
四、实现细节（边界防护）
- 初始化：
left = 0、right = (int)nums.size() - 1。 - 边界防护：上取整保证
mid >= 1（当left < right），nums[mid-1]永不越界；n == 1时循环不进入，直接返回 0（该元素即峰值）；相邻元素不相等保证判据无歧义。 - 复杂度：时间 O(log n)（每次排除一半），空间 O(1)（仅常数个变量）。
- 关键判断：
if (nums[mid - 1] > nums[mid]) right = mid - 1; else left = mid;（坡向收敛）、while (left < right)（循环边界）。
五、返回值（目标映射）
- 返回
left：任意一个峰值下标，对应题目"返回任何一个峰值所在位置"。
三.代码
class Solution { public: int findPeakElement(vector<int>& nums) { int left = 0; // 区间左端点 int right = (int)nums.size() - 1; // 区间右端点 // 1. 二段性二分：比较前邻元素，判断 mid 在上升段还是下降段 while (left < right) { // mid 上取整：保证 mid >= 1（nums[mid-1] 不越界），且配合 left = mid 防死循环 int mid = left + (right - left + 1) / 2; if (nums[mid - 1] > nums[mid]) { right = mid - 1; // 下降段：峰值在左半，丢弃右半（含 mid） } else { left = mid; // 上升段：峰值在右半（含 mid），向右收敛 } } // 2. 收敛点即峰值（峰值必然存在，无需校验） return left; } };四、易错点分析
难点1：mid 必须上取整，且这是nums[mid-1]安全的前提
int mid = left + (right - left + 1) / 2; // 上取整 if (nums[mid - 1] > nums[mid])本模板含left = mid向右收缩，必须上取整（否则相邻区间时 mid 取 left，left = mid卡死）。同时，上取整在left < right时保证mid >= left + 1 >= 1，因此nums[mid-1]永远不会访问下标 0 之前的元素。若误用下取整，left = mid死循环；若强行访问nums[mid-1]，mid=0 时越界。
难点2：判据方向与 852 题是镜像对称的
// 本题（162）：比较 nums[mid-1] 与 nums[mid] → 上取整 // 852 题： 比较 nums[mid] 与 nums[mid+1] → 下取整852 题用arr[mid] < arr[mid+1]判"上升"并left = mid + 1；本题用nums[mid-1] > nums[mid]判"下降"并right = mid - 1。两者判据互为镜像，取整方向也互为镜像。把 852 的模板原样搬来（下取整 + 比较 mid/mid+1）也能 AC 本题，但把比较方向抄错（如比较nums[mid] > nums[mid-1]却配错收缩方向）会收敛到错误的谷底。
难点3：为什么"上升段保留 mid"而不是跳过 mid
else { left = mid; // nums[mid-1] < nums[mid]：mid 可能是峰值，必须保留 }nums[mid-1] < nums[mid]只说明 mid 处于上升段，mid本身可能就是峰值（如[1,2,3]中 mid=2，2 的右侧没有元素，它就是边界峰值）。若写成left = mid + 1直接跳过 mid，可能漏掉恰好是峰值的 mid（尤其峰在边界时）。
难点4：边界元素峰值的处理（无需特判）
return left; // n=1 时 left=0，nums[0] 即峰值本题峰值定义对边界元素放宽（只需大于唯一邻居）。代码通过"往上升方向走"的性质隐式处理了边界峰值：若数组单调，二分会一路收敛到端点，端点即峰值，无需任何特判。若误以为必须写if (nums[0] > nums[1]) return 0之类的特判，反而画蛇添足、可能引入越界。
五、流程图
🎯 闭幕
🎉 恭喜你完成了「寻找峰值」问题的学习！
为了巩固知识并进一步拓展，建议你：
🚀动手实践
在 LeetCode 上提交代码，尝试不同的测试用例。
💡深入思考
当
nums[mid-1] > nums[mid]时，执行right = mid - 1；否则执行left = mid。为什么这个分支逻辑能保证峰值一定在收缩后的区间内？请从相邻元素的单调性角度解释。本题与山脉数组峰顶索引（LC 852）非常相似，但峰值定义更宽泛（可存在多个峰值，且不要求先增后减）。为什么 LC 852 中比较
arr[mid]与arr[mid+1]使用下取整，而本题比较nums[mid-1]与nums[mid]使用上取整？这两种写法的设计动机分别是什么？时间复杂度为 O(log n)，如果使用线性扫描找峰值，时间复杂度是多少？在
n = 10^5时，两种方法的效率差异有多大？
📚延伸挑战
如果问题改为寻找山谷（局部最小值），数组两端视为正无穷，你如何修改比较逻辑和收敛方向？
如果数组是二维矩阵，要求找出一个局部峰值（即该元素大于其上下左右相邻元素），你能否将一维二分的思想推广到二维？请描述核心思路。
如果你觉得本文对你有所帮助，欢迎：
👍点赞 / 收藏
👤关注作者，获取更多题解
💬留言交流你的疑问或优化思路
📌深入思考答案
分支逻辑依据：若
nums[mid-1] > nums[mid]，说明mid处于下降段（左邻更大），峰值在左半侧（包括mid-1），因此丢弃右半；否则nums[mid-1] < nums[mid]，说明mid处于上升段（右邻更大），峰值在右半侧（包括mid），向右收敛。两种写法的设计动机：LC 852 比较
arr[mid]与arr[mid+1]，用下取整配合right = mid，因为山脉数组严格先增后减，且峰值唯一；本题比较nums[mid-1]与nums[mid]，用上取整配合left = mid，因为峰值不唯一且两端视为负无穷，上取整能保证mid向右靠拢，更贴合“寻找任意峰值”的需求。线性扫描 O(n)，二分 O(log n)，
n=10^5时线性扫描需 10^5 次比较，二分仅约 17 次，效率显著提升。
🔍延伸挑战答案
挑战1：寻找局部最小值（山谷），只需将比较条件反置：若
nums[mid-1] < nums[mid]，谷底在左半（right = mid - 1）；否则谷底在右半（left = mid），其余逻辑不变。挑战2：二维找峰值，可对行做二分：找到中间行，在该行中找最大值列，然后比较该列上下元素，若上邻更大则向上收缩行区间，若下邻更大则向下收缩，直到找到峰值，时间复杂度 O(n log m) 或 O(m log n)。
祝你在算法之路上越走越稳，早日攻克每一道难题！下次见 🚀✨