【C++习题】22.二分查找算法_寻找峰值

文章目录

• • 题目链接：
  • 题目描述：
  • 解法
  • C++ 算法代码：
  • 图解

题目链接：

162. 寻找峰值

题目描述：

解法

暴力解法：

三种山峰的情况

1. 开始元素比它后面一个元素大的话直接就是山峰了（因为nums[-1] = nums[n] = -∞）
2. 普通山峰
3. 最后一个元素比前面一个元素大的话直接就是山峰了

二分算法：

首先要找二段性

C++ 算法代码：

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] > nums[mid - 1]) left = mid;
            else right = mid - 1;
        }
        return left;
    }
};

图解

例如：nums = [1,2,3,1]

1. left = 0, right = 2

   进入循环，mid=1

   nums[mid] > nums[mid - 1]，left = mid = 1

2. left = 1, right = 2

   进入循环，mid=2

   nums[mid] > nums[mid - 1]，left = mid = 2

3. left = 2, right = 2

   跳出循环，返回2