二分查找算法(5) _山脉数组的峰顶索引
个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创二分查找算法(5) _山脉数组的峰顶索引
收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论💌
目录
温馨提示:
1. 题目链接 :
2. 题目描述 :
3. 解法(二分查找) :
算法思路 :
代码展示 :
结果分析 :
4. 二分算法模板总结
温馨提示:
这道题是直接使用了二分模板,轻松拿捏了这道题,如果你还不知道的话,自行去下篇博客
---二分查找算法(2) _在排序数组中查找元素的第一个和最后一个_模板-CSDN博客
1. 题目链接 :
OJ链接: 山脉数组的峰顶索引
2. 题目描述 :
给定一个长度为 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 <= 1050 <= arr[i] <= 106- 题目数据 保证
arr是一个山脉数组
注意: 你必须设计并实现时间复杂度为
O(log(n))的解决方案。
3. 解法(二分查找) :
算法思路 :
这道题很明显想要我们使用二分算法去解决问题,可以题目中的数组不是有序数组这怎么使用二分啊?
其实大家不要思维固化二分算法,二分算法其实是利用数组的二段性,将数组不断分成两段,不断进行检索,数组有序只是数组二段性其中一个.
这里我们的数组看似无序,但是里面是由规律让山脉这个数组分成两段进行检索:
第一段: [0, 山顶] arr[i] > arr[i-1]
第二段: (山顶, 0] arr[i] < arr[i -1]
我们关键的条件判断出来后,直接调用我们的二分算法模板就行
代码展示 :
class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {//分成两部分//山底 --- 山顶 a[i] > a[i - 1]//山顶 --- 山底 a[i] < a[i - 1]//左右山底绝对不是山顶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 if(arr[mid] < arr[mid - 1]) right = mid - 1; }return left;}
};
结果分析 :
这里我们的算法时间复杂度为: log(N)满足题目要求.
4. 二分算法模板总结
这里再次强调一下我们的二分算法模板(真的很好用!!!)
while(left < right){int mid = left + (right - left) / 2;if(...) left = mid + 1;else right = mid;
}while(left < right){int mid = left + (right - left + 1) / 2;if(...) left = mid;else right = mid - 1;
}快速记忆:
分类讨论的代码,就题论题即可
下面出现-1,上面就+1,否侧不加