二分查找专题
在算法面试中，二分查找不仅用于有序数组，更常用于解决具有单调性或二段性的问题。今天通过两道经典题目，深入理解如何利用二分法高效定位极值。
1. 山峰数组的峰顶索引
题目链接： 852. 山脉数组的峰顶索引 - LeetCode
题目描述： 给定一个长度为 n 的山脉数组 arr，满足存在某个索引 i (0 < i < n-1)，使得数组先严格递增后严格递减。请找到这个峰顶索引 i。
解法思路： 暴力遍历虽然可行，但效率仅为 O(n)。利用山脉数组的单调性，我们可以将时间复杂度优化至 O(log n)。
观察峰顶位置及其两侧的数据特征：
- 峰顶左侧：呈上升趋势，即
arr[i] > arr[i-1]且arr[i] < arr[i+1] - 峰顶右侧：呈下降趋势，即
arr[i] < arr[i-1]且arr[i] > arr[i+1]
基于此，我们在二分查找过程中比较中间元素 mid 与其前一个元素 mid-1 的关系：
- 若
arr[mid] > arr[mid-1]，说明当前处于上升阶段，峰顶在 mid 或其右侧，因此令left = mid。 - 若
arr[mid] < arr[mid-1]，说明当前处于下降阶段，峰顶在 mid 左侧，因此令right = mid - 1。
注意边界处理，由于题目保证是山脉数组，左右端点不可能是峰顶，搜索范围可设为 [1, size-2]。
C++ 实现：
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int left = 1;
int 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;
}
};
2. 寻找峰值
题目链接： 162. 寻找峰值 - LeetCode
题目描述：
给定一个整数数组 nums，其中相邻元素不相等。峰值元素是指其值严格大于左右相邻值的元素。假设 nums[-1] = nums[n] = -∞，请找出任意一个峰值元素并返回其索引。
解法思路： 这道题同样可以利用二分查找，关键在于判断'二段性'。
任取一个点 i，比较它与下一个点 i+1 的大小：
- 如果
nums[i] > nums[i+1]，说明此处正在下降。由于最左侧可视作负无穷，那么左侧区域一定存在一个峰值（从负无穷上升到某点后下降）。此时去左侧寻找结果，令right = i。 - 如果
nums[i] < nums[i+1]，说明此处正在上升。同理，右侧区域一定存在一个峰值（从某点下降到负无穷）。此时去右侧寻找结果，令left = 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]) {
// 下降趋势，峰值在左侧（含 mid）
right = mid;
} else {
// 上升趋势，峰值在右侧（不含 mid）
left = mid + 1;
}
}
return left;
}
};
总结
这两道题展示了二分查找在处理非完全有序数据时的灵活性。核心在于识别局部单调性，从而确定搜索方向。在实际编码时，务必注意 mid 的计算方式以及边界条件的更新逻辑，防止死循环或越界。掌握这种'趋势判断'的二分思想，能帮助你解决更多变种的极值问题。
