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

基于此，我们可以通过比较 mid 与其前驱元素的大小关系来缩小搜索范围：

• 如果 arr[mid] > arr[mid - 1]，说明处于上升趋势，峰顶在右侧（包含 mid），令 left = mid。
• 如果 arr[mid] < arr[mid - 1]，说明处于下降趋势，峰顶在左侧（不包含 mid），令 right = mid - 1。

注意这里使用 left + (right - left + 1) / 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;
    }
};

时间复杂度： O(log n)，空间复杂度： O(1)。

022 寻找峰值

题目描述：

峰值元素是指其值严格大于左右相邻值的元素。数组可能包含多个峰值，返回任何一个即可。假设 nums[-1] = nums[n] = -∞。

算法思路：二分查找

这道题的关键在于发现「二段性」。对于任意一个点 i，我们只需比较它与下一个点 i + 1 的关系：

1. 若 arr[i] > arr[i + 1]：此时左侧区域一定存在峰值（因为最左侧是负无穷，且当前点在下降），结果在左侧。
2. 若 arr[i] < arr[i + 1]：此时右侧区域一定存在峰值（因为最右侧是负无穷，且当前点在上升），结果在右侧。

这种性质允许我们像普通二分查找一样不断缩小区间，最终收敛到一个峰值。

代码实现

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, 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;
    }
};

时间复杂度： O(log n)，空间复杂度： O(1)。

总结

这两道题展示了二分查找在处理非严格有序数组时的灵活性。核心技巧在于识别数据的单调性变化趋势，并利用它来指导搜索方向。在实际解题中，建议先画图分析边界条件，再编写代码，这样能有效避免死循环或越界问题。