二分查找实战：山峰数组峰顶索引与寻找峰值

流程解析

22. 寻找峰值

题目描述

题目示例

解法：二分查找

思路分析

这道题不需要找到全局最大值，只要找到一个局部峰值即可。关键在于利用数组两端可视作负无穷的假设。

任取一个点 i，比较它与下一个点 i+1：

• 如果 nums[i] > nums[i+1]，说明当前处于下降坡道，左侧必然存在一个峰值（因为最左边是负无穷），向左搜索。
• 如果 nums[i] < nums[i+1]，说明当前处于上升坡道，右侧必然存在一个峰值（因为最右边是负无穷），向右搜索。

一旦确定了这种二段性，就可以套用二分模板快速收敛。

C++ 实现

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < nums[mid + 1]) {
                // 上升阶段，峰值在右侧
                left = mid + 1;
            } else {
                // 下降阶段，峰值在左侧或当前位置
                right = mid;
            }
        }
        return left;
    }
};

流程解析

总结

这两道题都利用了二分查找的核心思想——通过比较中间状态来排除一半的搜索空间。山峰数组侧重于单调性的转折，而寻找峰值则利用了边界无穷大的特性。在实际编码中，务必注意 mid 的计算方式以及边界条件的更新，避免陷入死循环。理解这些细节后，面对类似的变体题目也能游刃有余。