二分查找实战：山峰数组峰顶索引与寻找峰值
在算法面试中，利用单调性或二段性进行二分查找是高频考点。今天我们来深入探讨两个经典问题：山脉数组的峰顶索引和寻找任意峰值。这两个问题看似不同，但核心逻辑都在于通过比较中间值与相邻元素的关系，快速缩小搜索范围。
1. 山脉数组的峰顶索引
题目描述
给定一个长度为 n 的山脉数组 arr，其中存在唯一的峰顶索引 i，满足：
- arr[0] < arr[1] < ... < arr[i]
- arr[i] > arr[i+1] > ... > arr[n-1]
我们需要找到这个峰顶索引 i。
解题思路
山脉数组具有明显的单调性特征：左侧严格递增，右侧严格递减。这意味着数组中存在一个分界点，使得前半部分满足 arr[mid] < arr[mid + 1]，后半部分满足 arr[mid] > arr[mid + 1]。
我们可以利用这一特性进行二分查找：
- 初始化左边界
left = 0，右边界right = arr.size()。 - 计算中间位置
mid。 - 如果
arr[mid] < arr[mid + 1]，说明当前处于上升阶段，峰顶在右侧，更新left = mid + 1。 - 否则，说明当前处于下降阶段或就是峰顶，更新
right = mid。 - 循环直到
left == right，此时即为峰顶索引。
这种写法实际上是在寻找第一个不满足 arr[mid] < arr[mid + 1] 的位置，即区间的右端点。
代码实现
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int left = 0;
int right = arr.size();
while (left < right) {
int mid = left + (right - left) / 2;
// 判断趋势：如果在上升段，峰顶肯定在右边
if (arr[mid] < arr[mid + 1]) {
left = mid + 1;
} else {
// 否则峰顶在左边或就是当前位置
right = mid;
}
}
return left;
}
};
注意： 这里的 mid 计算采用向下取整，配合 left = mid + 1 可以避免死循环。同时访问 mid + 1 时需注意边界，由于题目保证是山脉数组且长度至少为 3，mid 不会越界到最后一个元素。
2. 寻找峰值
题目描述
给定一个整数数组 nums，找到任意一个峰值并返回其索引。峰值元素是指其值大于左右相邻值的元素。假设 nums[-1] = nums[n] = -∞。
解题思路
与山脉数组不同，这里不需要整个数组先增后减，只需要找到一个局部极大值即可。关键在于理解'二段性'：
任取一个点 i，比较它与下一个点 i+1 的大小：
- 如果
nums[i] < nums[i+1]，说明处于上升趋势，根据边界条件（最左侧为负无穷），峰值一定存在于[i+1, end]区间内。 - 如果
nums[i] >= nums[i+1]，说明处于下降趋势或持平，峰值一定存在于[start, i]区间内。
因此，我们依然可以使用二分查找，每次将搜索空间减半。
代码实现
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;
}
};
关键点解析：
- 为什么
right = mid而不是mid - 1？因为当nums[mid] >= nums[mid+1]时，mid本身就有可能是峰值，不能排除。 - 为什么
left = mid + 1？因为当nums[mid] < nums[mid+1]时，mid肯定不是峰值，可以直接跳过。 - 时间复杂度均为 O(log n)，空间复杂度 O(1)。
总结
这两道题的核心都在于识别数组中的单调性变化。二分查找不仅仅是用于有序数组的查找，更适用于任何具备'二段性'的问题场景。在实际编码中，务必注意边界条件的处理以及 mid 的计算方式，避免死循环或越界访问。掌握这种思维模式，能帮助你解决更多复杂的搜索类问题。