【Leetcode每日一题】二分查找 - 山脉数组的峰顶索引（难度⭐⭐）（23）

1. 题目解析

Leetcode链接：852. 山脉数组的峰顶索引

这个问题的理解其实相当简单，只需看一下示例，基本就能明白其含义了。

核心在于找到题目中所说的峰值所在的下标并返回他们的下标即可。

2. 算法原理

峰顶及两侧数据特点分析

峰顶数据特点：

• 峰顶位置 arr[i] 的值大于其前后两个位置的值，即 arr[i] > arr[i - 1] 且 arr[i] > arr[i + 1]。

峰顶左侧数据特点：

• 峰顶左侧的数据呈现上升趋势，即 arr[i] 的值大于其左侧位置的值 arr[i - 1]，但小于其右侧位置的值 arr[i + 1]。

峰顶右侧数据特点：

• 峰顶右侧的数据呈现下降趋势，即 arr[i] 的值小于其左侧位置的值 arr[i - 1]，但大于其右侧位置的值 arr[i + 1]。

根据 mid 位置信息的搜索策略

上升趋势：

• 若 mid 位置的数据呈现上升趋势，则接下来应在 [mid + 1, right] 区间内继续搜索峰顶。

下降趋势：

• 若 mid 位置的数据呈现下降趋势，则接下来应在 [left, mid - 1] 区间内搜索峰顶。

峰顶位置：

• 若 mid 位置恰好是峰顶，则直接返回该位置作为结果。

3. 代码编写 

class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int l = 0, r = arr.size() - 1, m = -1;while(l < r){m = (l + r) / 2;if(arr[m] > arr[m + 1]) r = m;else l = m + 1;}return r;}
};

The Last

嗯，就是这样啦，文章到这里就结束啦，真心感谢你花时间来读。

觉得有点收获的话，不妨给我点个赞吧！

如果发现文章有啥漏洞或错误的地方，欢迎私信我或者在评论里提醒一声~