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

在算法面试中，二分查找不仅适用于有序数组，还能处理具有单调性的函数问题。今天我们来深入探讨两个经典的山峰类题目，它们都可以通过二分法将时间复杂度从 O(n) 优化至 O(log n)。

1. 山峰数组的峰顶索引

题目描述： 给定一个长度为 n 的山峰数组 arr，满足存在某个索引 i (0 < i < n - 1)，使得 arr[0] < arr[1] < ... < arr[i-1] < arr[i] > arr[i+1] > ... > arr[n-1]。请找到这个峰顶索引 i。

思路解析： 山峰数组具有明显的二段性：前半段递增，后半段递减。我们可以利用这一特性进行二分查找。

关键在于比较中间元素 mid 与其前一个元素 mid - 1 的关系：

• 如果 arr[mid] > arr[mid - 1]，说明当前处于上升阶段，峰顶一定在右侧（包含 mid），因此令 left = mid。
• 如果 arr[mid] < arr[mid - 1]，说明当前处于下降阶段，峰顶一定在左侧（不包含 mid），因此令 right = mid - 1。

注意边界条件，由于题目保证是山峰数组，首尾不可能是峰顶，所以初始范围可以设为 [1, size - 2]。

代码实现：

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;
    }
};

2. 寻找峰值

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

思路解析： 这道题比上一道更通用，不需要整个数组先增后减，只要找到一个局部极大值即可。核心依然在于判断'二段性'。

任取一点 i，比较 nums[i] 和 nums[i + 1]：

• 若 nums[mid] > nums[mid + 1]，说明当前位置处于下降趋势，那么左侧区域（包括 mid）必然存在一个峰值（因为最左侧是负无穷，必须有一个上升过程到达峰值），所以 。