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

21. 山峰数组的峰顶索引

题目链接

算法思路

解决这类问题的关键在于理解山脉数组的特性。峰顶元素同时大于其左右相邻值，左侧呈上升趋势，右侧呈下降趋势。这种单调性天然适合二分查找。

我们关注中间位置 mid 与其相邻元素的关系：

• 若 arr[mid] < arr[mid + 1]，说明处于上升阶段，峰值在右侧；
• 若 arr[mid] > arr[mid + 1]，说明处于下降阶段，峰值在左侧或即为当前点。

通过不断缩小搜索范围，最终收敛到峰顶索引。

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

22. 寻找峰值

题目链接

算法思路

这道题是上一题的泛化版本。虽然数组不一定严格先增后减，但题目保证存在峰值。任取一点 i，与 i+1 比较：

• 若 nums[i] < nums[i + 1]，说明右侧有更大值，且最右端为负无穷，故右侧必有峰值；
• 若 nums[i] > nums[i + 1]，说明左侧有更大值，且最左端为负无穷，故左侧必有峰值。

同样利用二段性进行二分查找。

C++ 算法代码

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
};