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

前言：

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

二分查找专题

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的平方根和搜索插入位置