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

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

在算法面试中，利用单调性进行二分查找是解决极值问题的常用手段。今天我们来梳理两道经典题目：山脉数组的峰顶索引（LeetCode 852）和寻找峰值（LeetCode 162）。这两题的核心都在于识别'二段性'，从而将线性搜索优化为对数级复杂度。

21. 山峰数组的峰顶索引

题目描述

给定一个长度为 n 的山脉数组 arr，其中存在某个索引 i 使得数组先严格递增后严格递减。请找到这个峰顶索引 i。

思路解析

既然数组呈现'先增后减'的趋势，那么对于任意位置 mid，我们只需要比较它与相邻元素的大小关系，就能判断它处于上升段还是下降段。

• 若 arr[mid] > arr[mid - 1]，说明当前位置处于上升阶段，峰顶一定在右侧（包含 mid），因此左边界可以移到 mid。
• 若 arr[mid] < arr[mid - 1]，说明当前位置已经过了峰顶，进入下降阶段，峰顶一定在左侧（不包含 mid），右边界应设为 mid - 1。

这里有个细节要注意：为了避免死循环，计算 mid 时采用向上取整的方式 (right - left + 1) / 2，这样当 left = right - 1 时，mid 会偏向右侧，配合 left = mid 的逻辑能确保收敛。

参考实现

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 1, right = arr.size() - 2;
        while (left < right) {
            // 向上取整，防止死循环
            int mid = left + (right - left + 1) / 2;
            if (arr[mid] > arr[mid - 1]) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

22. 寻找峰值

题目描述

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