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

山峰数组的峰顶索引

题目描述

给定一个长度为 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;
    }
};