二分查找：山峰数组的峰顶索引与寻找峰值
21. 山峰数组的峰顶索引
题目链接： 852. 山脉数组的峰顶索引 - 力扣（LeetCode）
题目描述： 给定一个长度为 n 的山脉数组 arr，其中存在某个索引 i 使得 arr[0] < arr[1] < ... < arr[i-1] < arr[i] > arr[i+1] > ... > arr[n-1]。返回该索引 i。
题目示例： （图片移除）
解法（二分查找）:
这里暴力解法大家自己实现一下，我就不实现了
算法思路：
分析峰顶位置的数据特点，以及山峰两旁的数据的特点：
- 峰顶数据特点：arr[i] > arr[i-1] && arr[i] > arr[i+1]
- 峰顶左边的数据特点：arr[i] > arr[i-1] && arr[i] < arr[i+1], 呈上升趋势
- 峰顶右边数据的特点：arr[i] < arr[i-1] && arr[i] > arr[i+1], 呈下降趋势
由此我们可以分为以下两种情况：
- 如果 mid 位置的值小于 mid-1 位置的值 left=mid；
- 如果 mid 位置的值大于 mid-1 位置的值 right=mid-1；
二分查找解法代码（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. 寻找峰值
题目链接： 162. 寻找峰值 - 力扣（LeetCode）
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。你可以假设 nums[-1] = nums[n] = -∞。
