二分查找实战：山峰数组峰顶索引与寻找峰值
在算法面试中，二分查找的应用远不止于简单的有序数组查找。当数据呈现某种特定的单调性或'二段性'时，我们依然可以利用二分思想来加速搜索。今天主要拆解两道基于二分查找的经典题目：山峰数组的峰顶索引和寻找峰值。
1. 山峰数组的峰顶索引
题目描述
给定一个长度为 n 的山脉数组 arr，其中存在某个索引 i (0 < i < n - 1) 满足：
- arr[0] < arr[1] < ... < arr[i]
- arr[i] > arr[i+1] > ... > arr[n-1]
我们需要找到这个峰顶索引 i。
解题思路
这道题的关键在于利用数组的单调性。虽然整个数组不是有序的，但我们可以将其视为两个有序部分：上升段和下降段。
观察中间位置 mid 与其相邻元素的关系：
- 如果
arr[mid] < arr[mid + 1]，说明当前处于上升阶段，峰值一定在右侧（包含 mid+1）。 - 如果
arr[mid] > arr[mid + 1]，说明当前处于下降阶段或已经是峰值，峰值一定在左侧（包含 mid）。
通过不断缩小搜索区间，最终 left 和 right 会收敛到同一个位置，即峰值索引。
C++ 实现
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int left = 0;
int right = arr.size();
while (left < right) {
// 使用向上取整避免死循环，确保 mid 偏向右侧
int mid = left + (right - left + 1) / 2;
// 比较 mid 与前一个元素，判断趋势
if (arr[mid - 1] < arr[mid]) {
// 上升趋势，峰值在右侧
left = mid;
} else {
// 下降趋势，峰值在左侧
right = mid - 1;
}
}
return left;
}
};
代码细节解析：
这里我选择了 [小于等于峰值], [大于峰值] 的区间划分方式。注意 mid 的计算使用了 (right - left + 1) / 2，这是为了防止 left 和 right 相邻时出现死循环。因为当 left = mid 时，如果 mid 计算偏左，left 永远不会增加。实际运行中，这种写法能更稳健地定位右边界。
2. 寻找峰值
题目描述
给定一个整数数组 nums，找到任意一个峰值元素的索引并返回。峰值元素是指其值严格大于左右相邻值的元素。假设 nums[-1] = nums[n] = -∞。
解题思路
这道题比上一道稍微抽象一些，它不要求整个数组是山脉形状，只要求找到一个局部峰值。核心依然是寻找'二段性'。
任取一个点 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;
// 比较 mid 与 mid + 1
if (nums[mid] < nums[mid + 1]) {
// 上升趋势，峰值在右侧
left = mid + 1;
} else {
// 下降趋势或峰值，峰值在左侧（含 mid）
right = mid;
}
}
return left;
}
};
代码细节解析：
这里的区间划分是 [小于峰值], [大于等于峰值]。注意 mid 的计算没有加 1，因为我们使用的是 left = mid + 1 来跳过当前点，所以不需要担心死循环问题。这种写法逻辑上更直观：只要右边比当前大，就往右跑；否则就停在左边找。
总结
这两道题的核心都在于识别'趋势'。一旦确定了哪一侧可能存在峰值，就可以果断舍弃另一侧。掌握这一模式有助于应对各类变体问题，比如旋转排序数组的最小值等。在实际编码时，务必注意边界条件和 mid 的计算方式，避免陷入死循环。
