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

或者采用找右端点的逻辑：

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        // 区间划分：[ 小于等于峰值 ], [ 大于峰值 ](相当于查找右端点)
        int left = 0;
        int right = arr.size();
        
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            
            // 对于偶数而言 mid 始终是在右边，所以判断条件是 arr[mid - 1] < arr[mid]
            if(arr[mid - 1] < arr[mid]) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

流程解析

22. 寻找峰值

题目描述

峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。你可以假设 nums[-1] = nums[n] = -∞。

题目示例

解题思路

这道题的关键在于理解'边界条件'。因为题目假设了数组两端是负无穷，这意味着只要数组中存在比相邻元素大的值，就一定能找到一个峰值。

任取一个点 i，与下一个点 i+1 比较，只有两种情况：

1. nums[i] > nums[i + 1]：此时左侧区域一定会存在山峰（因为最左侧是负无穷），那么我们就可以去左侧寻找结果。
2. nums[i] < nums[i + 1]：此时右侧区域一定会存在山峰（因为最右侧是负无穷），那么我们就可以去右侧寻找结果。

当我们找到这种'二段性'的时候，就可以尝试用二分查找算法来解决问题，时间复杂度可以优化到 O(log n)。

参考实现（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 {
                // 否则峰值在左侧（包括 mid 本身）
                right = mid;
            }
        }
        return left;
    }
};

流程解析