【优选算法必刷100题】第021~22题（二分查找算法）：山脉数组的峰顶索引、寻找峰值
🔥艾莉丝努力练剑：个人主页
❄专栏传送门：《C语言》、《数据结构与算法》、C/C++干货分享&学习过程记录、Linux操作系统编程详解、笔试/面试常见算法：从基础到进阶
⭐️为天地立心，为生民立命，为往圣继绝学，为万世开太平
🎬艾莉丝的简介：
🎬艾莉丝的算法专栏简介：
目录
021 山脉数组的峰顶索引
力扣链接：852. 山脉数组的峰顶索引
力扣题解链接：二分查找模版解决【山脉数组的峰顶索引】问题
题目描述：
1.1 思路一：暴力解法
1.1.1 算法思路
峰顶的特点：比两侧的元素都要大。
因此，我们可以遍历数组内的每一个元素，找到某一个元素比两边的元素大即可。
1.1.2 算法实现
代码演示如下——
class Solution { public: int peakIndexInMountainArray(vector<int>& arr) { int n = arr.size(); // 遍历数组内每⼀个元素，直到找到峰顶 for (int i = 1; i < n - 1; i++) // 峰顶满⾜的条件 if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) return i; // 为了处理 oj 需要控制所有路径都有返回值 return -1; } };时间复杂度：O(n)，空间复杂度：O(1)。
1.2 思路二：二分查找
1.2.1 算法思路
1、分析峰顶位置的数据特点，以及山峰两旁的数据的特点：
（1）峰顶数据特点:arr[ i ] > arr[i - 1] && arr[ i ] > arr[i + 1]]；
（2）峰顶左边的数据特点:arr[ i ] > arr[ i - 1] && arr[ i ] < arr[i + 1]，也就是呈现上升趋势；
（3）峰顶右边数据的特点：arr[ i ]＜arr[i- 1]&&arr[ i ] > arr[i + 1]，也就是呈现下降趋势。
2、因此，根据mid位置的信息，我们可以分为下面三种情况：
（1）如果mid位置呈现上升趋势，说明我们接下来要在[mid + 1，right]区间继续搜索；
（2）如果mid位置呈现下降趋势，说明我们接下来要在[left，mid - 1]区间搜索；
（3）如果mid位置就是山峰，直接返回结果。
1.2.2 算法实现
代码演示如下——
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; } };时间复杂度：O(logn)，空间复杂度：O(1)。
1.3 博主手记
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己能够推导很重要！
022 寻找峰值
力扣链接：162. 寻找峰值
力扣题解链接：二分查找模版解决【寻找峰值】问题
题目描述：
2.1 算法思路：二分查找
2.1.1 算法思路
寻找二段性——
任取一个点 i ，与下一个点i + 1，会有如下两种情况：
（1）arr[ i ] > arr[i + 1]：此时【左侧区域】一定会存在山峰（因为最左侧是负无穷），那么我们可以去左侧去寻找结果；
（2）arr[ i ] < arr[i + 1]：此时【右侧区域】一定会存在山峰（因为最右侧是负无穷），那么我们可以去右侧去寻找结果。
当我们找到【二段性】的时候，就可以尝试用【二分查找】算法来解决问题。
2.2 算法实现
代码演示如下——
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]) left = mid + 1; else right = mid; } return left; } };时间复杂度：O(logn)，空间复杂度：O(1)。
2.3 博主手记
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己能够推导很重要！
结尾
往期回顾：
【优选算法必刷100题】第019~20题（二分查找算法）：x 的平方根、搜索插入位置
结语：都看到这里啦！请大佬不要忘记给博主来个“一键四连”哦！
🗡博主在这里放了一只小狗，大家看完了摸摸小狗放松一下吧！🗡
૮₍ ˶ ˊ ᴥ ˋ˶₎ა
