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

艾莉丝努力练剑

发布于 2025-11-18 13:21:47

140

文章被收录于专栏：C / C++C / C++

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;
    }
};