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

二分查找是处理有序或具有单调性数据结构的利器。今天我们来通过两道经典题目，深入理解如何利用二分法在 O(log n) 时间内定位极值点。

山峰数组的峰顶索引

给定一个山脉数组，我们需要找到其峰顶元素的索引。山脉数组的定义是存在某个索引 i，使得左侧严格递增，右侧严格递减。

暴力遍历虽然可行，但既然数组具备单调性特征，二分查找才是正解。关键在于判断当前中间位置处于上升段还是下降段。如果 arr[mid] 大于前一个元素，说明我们还在爬坡阶段，峰顶肯定在右边（包括 mid）；反之，如果在下坡或者已经过了峰顶，则向左收缩。

具体实现时，左右边界初始化为 1 和 size-2，因为首尾不可能是峰顶。循环条件设为 left < right，避免死循环。当 arr[mid] > arr[mid-1] 时，将左边界移至 mid，否则右边界移到 mid-1。最终 left 即为答案。

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 1, right = arr.size() - 2;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (arr[mid] > arr[mid - 1]) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

寻找峰值

第二道题稍微抽象一点，要求找出任意一个峰值元素。峰值定义为大于相邻元素的值。数组两端可视作负无穷。

这道题的核心在于'二段性'。对于任意中间点 mid，比较它和下一个点 mid+1 的大小。如果 nums[mid] > nums[mid+1]，说明此刻处于下降趋势，那么峰值一定在左侧（包含 mid），因为左边有负无穷作为起点，必然存在一个高点；反之，如果 nums[mid] < nums[mid+1]，说明正在上升，峰值在右侧（不包含 mid）。

同样使用二分框架，边界为 0 到 size-1。若满足下降条件，右边界收至 mid；否则左边界推至 mid+1。循环结束时 left 指向的就是一个峰值位置。

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

这两道题展示了二分查找在处理局部极值问题时的通用模式：利用单调性或趋势判断搜索方向。掌握这种'找趋势'的思路，比死记硬背模板更重要。