《算法题讲解指南：优选算法-二分查找》--21.山峰数组的的峰顶索引，22.寻找峰值

🔥小叶-duck：个人主页

❄️个人专栏：《Data-Structure-Learning》

《C++入门到进阶&自我学习过程记录》《算法题讲解指南》--从优选到贪心

✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游

目录

21. 山峰数组的的峰顶索引

题目链接：

题目描述：

题目示例：

解法（二分查找）:

算法思路：

C++算法代码：

算法总结及流程解析：

22. 寻找峰值

题目链接：

题目描述：

题目示例：

解法（二分查找）：

算法思路：

C++算法代码：

算法总结及流程解析：

结束语

21. 山峰数组的的峰顶索引

题目链接：

852. 山脉数组的峰顶索引 - 力扣（LeetCode）

题目描述：

题目示例：

解法（二分查找）:

算法思路：

      分析峰顶位置的数据特点，以及山峰两旁的数据的特点：

• 峰顶数据特点：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 = 0; int right = arr.size(); // while(left < right) // { // int mid = left + (right - left) / 2; // //对于偶数而言mid始终是在左边，所以判断条件是arr[mid] < arr[mid + 1] // if(arr[mid] < arr[mid + 1]) // { // left = mid + 1; // } // else // { // right = mid; // } // } // return left; //区间划分：[ 小于等于峰值 ], [ 大于峰值 ](相当于查找右端点) int left = 0; int right = arr.size(); while(left < right) { int mid = left + (right - left + 1) / 2; //对于偶数而言mid始终是在右边，所以判断条件是arr[mid - 1] < arr[mid] if(arr[mid - 1] < arr[mid]) { left = mid; } else { right = mid - 1; } } return left; } };

算法总结及流程解析：

22. 寻找峰值

题目链接：

162. 寻找峰值 - 力扣（LeetCode）

题目描述：

题目示例：

解法（二分查找）：

算法思路：

      寻找二段性：任取一个点 i，与下一个点 i+1，会有如下两种情况：

• arr[ i ] > arr[ i + 1 ]：此时【左侧区域】一定会存在山峰（因为最左侧是负无穷），那么我们就可以去左侧寻找结果
• arr[ i ] < arr[ i + 1 ]：此时【右侧区域】一定会存在山峰（因为最右侧是负无穷），那么我们就可以去右侧寻找结果

      当我们找到【二段性】的时候，就可以尝试用【二分查找】算法来解决问题。

C++算法代码：

class Solution { public: int findPeakElement(vector<int>& nums) { int left = 0; int 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; } };

算法总结及流程解析：

结束语

      到此，21.山峰数组的的峰顶索引，22.寻找峰值 这两道算法题就讲解完了。以题带点，详细分析了山峰数组的特性：峰顶同时大于左右相邻值，左侧呈上升趋势，右侧呈下降趋势。解题时抓住"二段性"特征，通过比较中间值与相邻元素的关系，逐步缩小搜索范围。希望大家能有所收获！