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

山峰数组的峰顶索引

题目描述

给定一个长度为 n 的山峰数组 arr，满足：

• arr.length >= 3
• 存在 i (0 < i < arr.length - 1) 使得 arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

找出任意一个满足条件的索引 i。

参考链接：852. 山脉数组的峰顶索引 - LeetCode

解题思路

这道题的核心在于利用'二段性'进行二分查找。观察数组特性，在峰值左侧是严格递增的，右侧是严格递减的。

我们可以根据中间值 mid 与其后一个值 mid + 1 的关系来判断当前处于哪一段：

• 如果 arr[mid] < arr[mid + 1]，说明 mid 处于上升坡，峰值一定在 mid 右侧（包含 mid + 1）。
• 如果 arr[mid] > arr[mid + 1]，说明 mid 处于下降坡，或者就是峰值本身，峰值一定在 mid 左侧（包含 mid）。

注意边界条件，由于题目保证是山脉数组，不需要额外检查左右边界是否越界。

C++ 实现

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0;
        int right = arr.size() - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            // 如果中间值小于右边，说明在上升阶段，峰值在右侧
            if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                // 否则在下降阶段或就是峰值，峰值在左侧（含 mid）
                right = mid;
            }
        }
        return left;
    }
};

寻找峰值

题目描述

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。你可以假设 nums[-1] = nums[n] = -∞。

参考链接：162. 寻找峰值 - LeetCode

解题思路

虽然题目允许返回任意峰值，但本质上还是寻找局部极大值。同样可以利用二分查找优化时间复杂度到 O(log n)。

关键在于理解'二段性'：对于任意位置 i，如果 nums[i] < nums[i+1]，说明右侧有上升趋势，且最右侧是负无穷，那么右侧必然存在一个峰值；反之，如果 nums[i] > nums[i+1]，说明左侧有上升趋势，左侧必然存在峰值。

因此，每次比较 mid 和 mid+1：

• 若 nums[mid] < nums[mid+1]，去右半边找。
• 若 nums[mid] > nums[mid+1]，去左半边找（mid 可能是峰值）。

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

总结

这两道题都利用了二分查找的特性，将线性扫描 O(n) 优化为对数级 O(log n)。核心技巧在于通过比较相邻元素确定搜索方向，无需遍历整个数组。在实际工程中，面对有序或半有序数据时，优先考虑此类分治策略。