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

二分查找专题

在算法面试中，二分查找不仅用于有序数组，更常用于解决具有单调性或二段性的问题。今天通过两道经典题目，深入理解如何利用二分法高效定位极值。

1. 山峰数组的峰顶索引

题目链接： 852. 山脉数组的峰顶索引 - LeetCode

题目描述： 给定一个长度为 n 的山脉数组 arr，满足存在某个索引 i (0 < i < n-1)，使得数组先严格递增后严格递减。请找到这个峰顶索引 i。

解法思路： 暴力遍历虽然可行，但效率仅为 O(n)。利用山脉数组的单调性，我们可以将时间复杂度优化至 O(log n)。

观察峰顶位置及其两侧的数据特征：

• 峰顶左侧：呈上升趋势，即 arr[i] > arr[i-1] 且 arr[i] < arr[i+1]
• 峰顶右侧：呈下降趋势，即 arr[i] < arr[i-1] 且 arr[i] > arr[i+1]

基于此，我们在二分查找过程中比较中间元素 mid 与其前一个元素 mid-1 的关系：

• 若 arr[mid] > arr[mid-1]，说明当前处于上升阶段，峰顶在 mid 或其右侧，因此令 left = mid。
• 若 arr[mid] < arr[mid-1]，说明当前处于下降阶段，峰顶在 mid 左侧，因此令 right = mid - 1。

注意边界处理，由于题目保证是山脉数组，左右端点不可能是峰顶，搜索范围可设为 [1, size-2]。

C++ 实现：

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 1;
        int 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;
            }
        }
         left;
    }
};