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

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

二分查找不仅适用于有序数组，在具有特定单调性的结构中同样高效。今天分享两道经典题目：山峰数组的峰顶索引和寻找峰值。它们的核心都在于利用数据的二段性特征，将线性搜索优化为对数级复杂度。

21. 山峰数组的峰顶索引

题目描述

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

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

我们需要找到这个峰顶索引 i。

解题思路

分析峰顶位置的数据特点，以及山峰两旁的数据趋势：

• 峰顶：arr[i] > arr[i-1] 且 arr[i] > arr[i+1]
• 左侧（上升）：arr[i] < arr[i+1]
• 右侧（下降）：arr[i] > arr[i+1]

因此，我们可以通过比较中间值 mid 与其相邻元素的关系来判断当前处于哪一段：

• 如果 arr[mid] < arr[mid + 1]，说明我们正处于上升阶段，峰值一定在 mid 右侧（包含 mid+1）。
• 如果 arr[mid] > arr[mid + 1]，说明我们正处于下降阶段或就在峰顶，峰值在 mid 左侧（包含 mid）。

这种判断条件天然构成了二分查找所需的'二段性'。

C++ 代码实现

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0;
        int right = arr.size();
        
        while(left < right) {
            int mid = left + (right - left) / 2;
            
            // 对于偶数而言 mid 始终是在左边，所以判断条件是 arr[mid] < arr[mid + 1]
            if(arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
};