21. 山峰数组的峰顶索引
题目描述： 给定一个长度为 n 的山脉数组 arr，其中存在某个索引 i (0 < i < n - 1) 使得：
- arr[0] < arr[1] < ... < arr[i]
- arr[i] > arr[i+1] > ... > arr[n-1]
请返回满足条件的峰顶索引 i。
算法思路： 暴力遍历虽然可行，但效率较低。利用山脉数组先增后减的特性，我们可以使用二分查找将时间复杂度优化至 O(log n)。
关键在于判断 mid 位置处于上升段还是下降段：
- 若 arr[mid] > arr[mid-1]，说明 mid 位于上升段或就是峰顶，目标在 [mid, right] 区间；
- 若 arr[mid] < arr[mid-1]，说明 mid 位于下降段，目标在 [left, mid-1] 区间。
注意边界处理，由于峰顶不在两端，初始搜索范围可设为 [1, n-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] = -∞。
算法思路： 这道题同样可以利用二分查找解决。核心在于识别'二段性'：对于任意中间点 mid，比较它与相邻元素的大小关系。
- 如果 nums[mid] > nums[mid+1]，说明当前处于下降趋势，峰值一定在左侧（包括 mid）；
- 如果 nums[mid] < nums[mid+1]，说明当前处于上升趋势，峰值一定在右侧（不包括 mid）。
通过不断缩小搜索区间，最终 left 和 right 会收敛到同一个峰值位置。
C++ 代码实现：
class Solution {
:
{
left = , right = nums.() - ;
(left < right) {
mid = left + (right - left) / ;
(nums[mid] > nums[mid + ]) {
right = mid;
} {
left = mid + ;
}
}
left;
}
};
