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

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

1. 山峰数组的峰顶索引

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

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

请找到并返回该峰顶索引 i。

解题思路： 暴力遍历虽然可行，但效率较低。观察山脉数组的特性，数据呈现先增后减的趋势，这天然具备二段性，适合使用二分查找将时间复杂度优化至 O(log n)。

关键在于判断 mid 位置处于上升段还是下降段：

• 上升段：arr[mid] < arr[mid + 1]，说明峰顶在右侧（包含 mid+1）。
• 下降段：arr[mid] > arr[mid + 1]，说明峰顶在左侧（包含 mid）。

为了处理边界情况，我们通常将搜索范围限制在 [1, n-2]，避免访问越界。

代码实现：

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

2. 寻找峰值

题目描述： 峰值元素是指其值严格大于左右相邻值的元素。给定一个整数数组 nums，找到任意一个峰值元素并返回其索引。