【优选算法必刷100题】第021-022题（二分查找）：山峰数组的的峰顶索引、寻找峰值

🔥个人主页：Cx330🌸

❄️个人专栏：《C语言》《LeetCode刷题集》《数据结构-初阶》《C++知识分享》

《优选算法指南-必刷经典100题》《Linux操作系统》:从入门到入魔

🌟心向往之行必能至

🎥Cx330🌸的简介：

目录

前言：

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

解法（二分查找）:

算法思路：

二分查找解法代码（C++）：

22. 寻找峰值

解法（二分查找）：

算法思路：

二分查找解法代码（C++）：

总结：

前言：

聚焦算法题实战，系统讲解三大核心板块：“精准定位最优解”——优选算法，“简化逻辑表达，系统性探索与剪枝优化”——递归与回溯，“以局部最优换全局高效”——贪心算法，讲解思路与代码实现，帮助大家快速提升代码能力

二分查找专题

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

题目链接：

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

题目描述：

题目示例：

解法（二分查找）:

这里暴力解法大家自己实现一下，我就不实现了

算法思路：

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

• 峰顶数据特点：arr[ i ] > arr[ i-1 ] &&[ 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=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; } };

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,right=nums.size()-1; while(left<right) { int mid=left+(right-left)/2; if(nums[mid]>nums[mid+1]) right=mid; else left=mid+1; } return left; } };

总结：

往期回顾：【优选算法必刷100题】第019-020题：x的平方根和搜索插入位置