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

21. 山峰数组的峰顶索引

题目描述： 给定一个长度为 n 的山脉数组 arr，其中存在某个索引 i (0 < i < n - 1) 使得：

• arr[0] < arr[1] < ... < arr[i]
• arr[i] > arr[i+1] > ... > arr[n-1]

请返回满足条件的峰顶索引 i。

算法思路： 暴力遍历虽然可行，但效率较低。利用山脉数组先增后减的特性，我们可以使用二分查找将时间复杂度优化至 O(log n)。

关键在于判断 mid 位置处于上升段还是下降段：

• 若 arr[mid] > arr[mid-1]，说明 mid 位于上升段或就是峰顶，目标在 [mid, right] 区间；
• 若 arr[mid] < arr[mid-1]，说明 mid 位于下降段，目标在 [left, mid-1] 区间。

注意边界处理，由于峰顶不在两端，初始搜索范围可设为 [1, n-2]。

C++ 代码实现：

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;
    }
};

22. 寻找峰值

题目描述： 给定一个整数数组 nums，找到任意一个峰值元素并返回其索引。数组可能包含多个峰值，返回任何一个即可。假设 nums[-1] = nums[n] = -∞。

算法思路： 这道题同样可以利用二分查找解决。核心在于识别'二段性'：对于任意中间点 mid，比较它与相邻元素的大小关系。

• 如果 nums[mid] > nums[mid+1]，说明当前处于下降趋势，峰值一定在左侧（包括 mid）；
• 如果 nums[mid] < nums[mid+1]，说明当前处于上升趋势，峰值一定在右侧（不包括 mid）。

通过不断缩小搜索区间，最终 left 和 right 会收敛到同一个峰值位置。

C++ 代码实现：

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;
    }
};

总结

这两个问题展示了二分查找在处理局部极值时的强大能力。与普通二分查找不同，这里不需要完全有序，只需要具备单调性或二段性特征即可。掌握这种'根据趋势收缩区间'的思路，能解决许多看似无序的搜索问题。