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

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

21. 山峰数组的峰顶索引

题目链接： LeetCode 852

题目描述： 给定一个长度为 n 的山脉数组 arr，满足存在 i 使得 arr[0] < ... < arr[i] > ... > arr[n-1]。返回任意峰顶索引 i。

解题思路： 既然数组具有明显的单调性特征——先增后减，这天然适合二分查找。我们不需要遍历所有元素，只需关注 mid 位置的斜率。

如果 arr[mid] < arr[mid + 1]，说明处于上升阶段，峰值一定在 mid 右侧（不含 mid）。 如果 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;
    }
};

22. 寻找峰值

题目链接： LeetCode 162

题目描述： 给定一个整数数组 nums，找到任意一个峰值元素并返回其索引。假设 nums[-1] = nums[n] = -∞。

解题思路： 这道题比上一道更通用，因为数组不一定严格先增后减，只要有一个局部极大值即可。核心依然是利用'二段性'。

任取一点 mid，比较它与右边邻居 mid+1：

1. 若 nums[mid] > nums[mid + 1]，说明此处正在下坡，峰值必然在左侧（包括 mid 本身）。