21. 山峰数组的峰顶索引
题目描述： 给定一个长度为 n 的山脉数组 arr，其中存在某个索引 i 使得 arr[0] < arr[1] < ... < arr[i-1] < arr[i] > arr[i+1] > ... > arr[n-1]。请找到这个峰顶索引 i。
算法思路： 暴力遍历虽然可行，但效率较低。既然数组具有明显的单调性特征（先增后减），我们可以利用二分查找将时间复杂度优化到 O(log n)。
关键在于判断当前 mid 位置处于上升段还是下降段：
- 如果
arr[mid] > arr[mid-1]，说明当前位置在上升坡或者就是峰顶，目标索引一定在 mid 及其右侧。 - 如果
arr[mid] < arr[mid-1]，说明已经过了峰顶进入下坡路，目标索引一定在左侧。
注意边界处理，由于峰顶不可能在首尾，搜索范围初始化为 [1, size-2]。
C++ 代码实现：
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;
}
};
22. 寻找峰值
题目描述： 给定一个整数数组 nums，找到任意一个峰值元素并返回其索引。数组可能包含多个峰值，返回任何一个即可。假设 nums[-1] = nums[n] = -∞。
算法思路： 这道题比上一道更通用，不要求整个数组是山脉形状，只要求局部极大值。核心思想依然是利用'二段性'进行二分。
任取一点 i 与 i+1 比较：
- 若
nums[i] > nums[i+1]，说明此处正在下降，根据边界负无穷的性质，左侧必然存在一个峰值。 - 若
nums[i] < nums[i+1]，说明此处正在上升，右侧必然存在一个峰值。
通过不断缩小区间，最终 left 和 right 会收敛到同一个峰值索引。
C++ 代码实现：
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]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
};
总结
这两个问题展示了二分查找在处理有序或半有序数据时的强大能力。解题的关键在于准确定义'二段性'，即如何根据中间状态决定搜索方向。在实际编码中，务必注意 mid 的计算方式以及左右边界的更新逻辑，避免死循环或越界。掌握这类模式后，类似的变体问题也能迎刃而解。