21. 山峰数组的峰顶索引
题目链接
题目描述
给定一个整数数组 arr，它是一个山脉数组，即存在索引 i 使得：
arr[0] < arr[1] < ... < arr[i]arr[i] > arr[i+1] > ... > arr[arr.length - 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位置的值，说明处于下降段，峰值在左侧，令right = mid； - 如果
mid位置的值大于mid-1位置的值，说明处于上升段或到达峰值，峰值在右侧或即为mid，令left = mid。
二分查找解法代码（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;
}
}
left;
}
};
