题目
链接:leetcode链接
思路分析(二分算法)
题目的提示已经非常明显了,使用O(logN)的算法,那就是二分算法。
如何寻找二段性?
观察数据,可以发现,需要找的峰顶索引的左右两侧数据有不同的特征
峰顶索引左边的数据都比前一个数据大
峰顶索引右边的数据都比前一个数据小
根据此二段性,我们就可以设计出二分算法了
细节:
- left < right(不用等号)
- mid = left + (right - left + 1) / 2 ( 寻找右边界)
代码
int peakIndexInMountainArray(vector<int>& arr) {int left = 0,right = arr.size() - 1;while(left < right){int mid = left + (right - left + 1) /2;if(arr[mid] > arr[mid - 1]) left = mid;else right = mid - 1;}return left;}