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

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

在算法面试中，利用单调性或二段性进行二分查找是高频考点。今天我们来深入探讨两个经典问题：山脉数组的峰顶索引和寻找任意峰值。这两个问题看似不同，但核心逻辑都在于通过比较中间值与相邻元素的关系，快速缩小搜索范围。

1. 山脉数组的峰顶索引

题目描述

给定一个长度为 n 的山脉数组 arr，其中存在唯一的峰顶索引 i，满足：

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

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

解题思路

山脉数组具有明显的单调性特征：左侧严格递增，右侧严格递减。这意味着数组中存在一个分界点，使得前半部分满足 arr[mid] < arr[mid + 1]，后半部分满足 arr[mid] > arr[mid + 1]。

我们可以利用这一特性进行二分查找：

1. 初始化左边界 left = 0，右边界 right = arr.size()。
2. 计算中间位置 mid。
3. 如果 arr[mid] < arr[mid + 1]，说明当前处于上升阶段，峰顶在右侧，更新 left = mid + 1。
4. 否则，说明当前处于下降阶段或就是峰顶，更新 right = mid。
5. 循环直到 left == right，此时即为峰顶索引。

这种写法实际上是在寻找第一个不满足 arr[mid] < arr[mid + 1] 的位置，即区间的右端点。

代码实现

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

注意： 这里的 mid 计算采用向下取整，配合 可以避免死循环。同时访问 时需注意边界，由于题目保证是山脉数组且长度至少为 3， 不会越界到最后一个元素。