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

注意：代码中使用了 arr[mid] < arr[mid + 1] 作为判断依据。由于题目保证是山脉数组，mid + 1 不会越界（因为 right 初始化为 size()，循环条件 left < right 保证了 mid 最大为 size() - 2）。

22. 寻找峰值

题目描述

峰值元素是指其值严格大于左右相邻值的元素。给定一个整数数组 nums，找到任意一个峰值元素的索引并返回。

假设 nums[-1] = nums[n] = -∞，且 nums[i] != nums[i + 1]。

解题思路

这道题比上一题更通用，因为它不要求整个数组先增后减，只要求找到一个局部极大值。

关键依然在于发现'二段性'。对于任意一点 mid，我们只需要比较它与右边邻居 mid + 1 的关系：

1. 若 nums[mid] < nums[mid + 1]：说明右侧有上升趋势。由于最右侧边界视为负无穷，那么右侧必然存在一个峰值。此时可以丢弃左半部分，在 [mid + 1, right] 继续查找。
2. 若 nums[mid] > nums[mid + 1]：说明右侧开始下降。由于最左侧边界视为负无穷，那么左侧（包含 mid）必然存在一个峰值。此时可以丢弃右半部分，在 [left, mid] 继续查找。

通过不断缩小区间，最终 left == right 时，该位置即为一个峰值。

C++ 实现

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1; // 使用闭区间 [left, right]
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            // 比较 mid 和 mid+1
            if (nums[mid] < nums[mid + 1]) {
                // 上升趋势，峰值在右侧
                left = mid + 1;
            } else {
                // 下降趋势，峰值在左侧（含 mid）
                right = mid;
            }
        }
        return left;
    }
};

总结

这两道题展示了二分查找在处理非完全有序数据时的强大能力。核心技巧在于：不要试图一次性理解全局，而是关注局部单调性。只要能够证明在某一侧必然存在解（基于边界条件如负无穷），就可以安全地舍弃另一侧。在实际编码中，注意区间的开闭定义以及 mid 的计算方式，避免死循环或越界。

掌握这种'二段性'思维，能帮你解决更多看似复杂实则可二分的问题。