二分搜索（四）山脉数组的峰顶索引

目录

 852. 山脉数组的峰顶索引

暴力

​二分优化

 162. 寻找峰值

---

 852. 山脉数组的峰顶索引

给定一个长度为 n 的整数 山脉 数组 arr ，其中的值递增到一个 峰值元素 然后递减。

返回峰值元素的下标。

你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。

示例 1：

输入：arr = [0,1,0]
输出：1

示例 2：

输入：arr = [0,2,1,0]
输出：1

示例 3：

输入：arr = [0,10,5,2]
输出：1

提示：

• 3 <= arr.length <= 105
• 0 <= arr[i] <= 106
• 题目数据 保证 arr 是一个山脉数组

 暴力

遍历一遍数组，若该位置能满足大于前面数小于后面数即可

class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {for(int i = 1; i < arr.size()-2; i++)// 注意遍历范围{if(arr[i] > arr[0] && arr[i] > arr[i+1])return i;}return -1;}
};

 二分优化

利用山峰特性，只要当前位置元素大于后面位置元素即可，当然也可以利用当前位置元素大于前面位置元素。俩种比较方式选择一种就行。

class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int left = 1, right = arr.size()-2; // 此题注意边界值选定，该山峰一定存在while(left < right)                 // 所以肯定不会在最左最右位置{int mid = left + (right - left)/2;if(arr[mid] > arr[mid+1]) // 判断当前位置和下一个位置的关系right = mid;          // 然后进行更新left。rightelseleft = mid + 1;}return right; // 最终left与right重叠，返回哪个都可以}
};

 162. 寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5 
解释：你的函数可以返回索引 1，其峰值元素为 2；或者返回索引 5， 其峰值元素为 6。

提示：

• 1 <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1
• 对于所有有效的 i 都有 nums[i] != nums[i + 1]

 和上面题几乎一致，唯一不同的地方就在与遍历条件范围不一样，此题可以访问到最左右俩侧元素。

class Solution {
public:int findPeakElement(vector<int>& nums) {int left = 0, right = nums.size() - 1; // 和之前题条件不一样while(left < right){int mid = left + (right - left) / 2;if(nums[mid] > nums[mid + 1])right = mid;elseleft = mid + 1;}return left;}
};