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

21. 山峰数组的峰顶索引

题目描述

题目示例

解法：二分查找

思路分析

观察山峰数组的特性，峰顶位置满足 arr[i] > arr[i-1] && arr[i] > arr[i+1]。其左侧呈上升趋势（arr[i] < arr[i+1]），右侧呈下降趋势（arr[i] > arr[i+1]）。这种单调性变化构成了典型的'二段性'，非常适合用二分查找来定位转折点。

具体策略如下：

• 若 mid 位置的值小于 mid+1 位置的值，说明处于上升阶段，峰顶在右侧，调整左边界。
• 若 mid 位置的值大于 mid+1 位置的值，说明处于下降阶段或已是峰顶，调整右边界。

C++ 实现

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0;
        int right = arr.size();
        while(left < right) {
            // 向上取整防止死循环，当 left + 1 == right 时 mid = right
            int mid = left + (right - left + 1) / 2;
            
            // 判断 mid 是否处于上升段
            if(arr[mid - 1] < arr[mid]) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

流程解析

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 的计算方式以及边界条件的更新，避免陷入死循环。理解这些细节后，面对类似的变体题目也能游刃有余。