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

21. 山峰数组的峰顶索引

题目描述

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

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

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

解题思路

这道题的关键在于利用数据的单调性。山脉数组具有明显的二段性：

• 在峰顶左侧，元素呈上升趋势（arr[mid] < arr[mid + 1]）；
• 在峰顶右侧，元素呈下降趋势（arr[mid] > arr[mid + 1]）。

因此，我们可以通过比较中间值与其相邻值的大小关系，判断当前处于上升段还是下降段，从而将搜索范围缩小一半。

具体策略如下：

• 若 arr[mid] < arr[mid + 1]，说明 mid 位于上升坡，峰顶在右侧，令 left = mid + 1；
• 若 arr[mid] > arr[mid + 1]，说明 mid 位于下降坡或就是峰顶，峰顶在左侧（含 mid），令 right = mid。

注意：由于题目保证是有效山脉数组，无需处理越界情况，但代码实现时需注意整数溢出和边界条件。

C++ 算法代码

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0;
        int right = arr.size() - 1;
        
        while (left < right) {
            // 防止死循环，mid 偏向右侧
            int mid = left + (right - left + 1) / 2;
            
            if (arr[mid - 1] < arr[mid]) {
                // 处于上升阶段，峰顶在右侧
                left = mid;
            } else {
                // 处于下降阶段，峰顶在左侧
                right = mid - ;
            }
        }
         left;
    }
};