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

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

在算法面试中，利用单调性进行二分查找是解决'峰值'类问题的经典套路。今天我们来拆解两道典型题目：山脉数组的峰顶索引（LeetCode 852）和寻找峰值（LeetCode 162）。

852. 山脉数组的峰顶索引

题目描述

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

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

我们需要找到这个峰顶索引 i。

核心思路

分析峰顶位置的数据特点，以及山峰两旁的数据特征：

• 峰顶：arr[i] > arr[i-1] 且 arr[i] > arr[i+1]
• 左侧：呈上升趋势，arr[i] < arr[i+1]
• 右侧：呈下降趋势，arr[i] > arr[i+1]

因此，我们可以根据中间值 mid 与其相邻元素的关系来判断峰值所在的区间：

1. 如果 arr[mid] < arr[mid + 1]，说明处于上升坡段，峰值一定在 mid 右侧，令 left = mid + 1。
2. 如果 arr[mid] > arr[mid + 1]，说明处于下降坡段或就是峰值，峰值在 mid 或其左侧，令 right = mid。

注意边界处理，通常采用左闭右开区间 [left, right) 来避免死循环。

C++ 参考实现

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0;
        int right = arr.size();
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 判断是否在上升阶段
            if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
};

流程解析

上述代码采用了左闭右开区间 [left, right)。当 mid 指向上升段时，mid 肯定不是峰值，所以 移到 。当 指向下降段时， 可能是峰值，所以 收缩到 。最终 时即为峰值位置。