前言
二分查找不仅适用于有序数组，在满足特定单调性的场景下同样高效。本文通过两道经典题目，探讨如何利用二分思想快速定位数组中的峰值。
21. 山峰数组的峰顶索引
题目描述：
给定一个长度为 n 的山脉数组 arr，其中存在唯一的峰顶索引 i，使得数组先严格递增后严格递减。即 arr[0] < arr[1] < ... < arr[i-1] < arr[i] > arr[i+1] > ... > arr[n-1]。请返回该峰顶索引。
算法思路： 这道题的关键在于识别'二段性'。虽然整个数组不是有序的，但相对于峰顶位置，它呈现出明显的两段特征：
- 左侧区间
[0, peak]是递增的，即arr[mid] < arr[mid + 1] - 右侧区间
[peak, n-1]是递减的，即arr[mid] > arr[mid + 1]
利用这一特性，我们可以用二分查找来逼近峰顶。如果中间元素比右边元素大，说明处于下降段，峰顶在左侧（包含 mid）；反之则处于上升段，峰顶在右侧（mid 右侧）。
注意边界处理，由于首尾不可能是峰顶，搜索范围可设为 [1, n-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;
}
};
22. 寻找峰值
题目描述：
给定一个整数数组 nums，找到任意一个峰值并返回其索引。峰值元素是指其值大于左右相邻值的元素。假设 nums[-1] = nums[n] = -∞。
算法思路：
这道题比上一道更灵活，因为数组不一定呈山脉状，只要找到一个局部极大值即可。核心逻辑依然是利用'二段性'：
任取一点 i，比较 nums[i] 和 nums[i+1]：
- 若
nums[i] > nums[i+1]，说明当前处于下降趋势，左侧一定存在峰值（因为最左端可视作负无穷），向左搜索。
