山脉数组的峰顶索引
题目描述: 给定一个长度为 n 的山脉数组 arr,其中存在某个下标 i(0 < i < n - 1)满足: arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[n - 1]。 请找到并返回该数组中任意一个峰顶索引 i。
题目链接: 852. 山脉数组的峰顶索引 - LeetCode
示例:

解法思路: 这道题的核心在于利用'二段性'进行二分查找。山脉数组具有明显的单调性特征:先严格递增,到达峰顶后严格递减。 我们观察中间位置 mid 与其右侧元素 mid + 1 的关系:
- 如果 arr[mid] < arr[mid + 1],说明当前位置处于上升阶段,峰顶一定在 mid 的右侧;
- 如果 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) {
int mid = left + (right - left) / 2;
// 判断趋势:若 mid 小于右侧,说明在爬坡,去右边找
if(arr[mid] < arr[mid + 1]) {
left = mid + 1;
} else {
// 否则在坡顶或下坡,锁定左边界
right = mid;
}
}
return left;
}
};
流程解析:





