852. 山脉数组的峰顶索引 - 力扣(LeetCode)
解法:二分查找
思路:O(logn)的时间复杂度,很可能是二分法,再看看有没有二段性:
由题目可以知道,i的左边比i小,右边比i大,所以数组具有二段性->二分法没跑了,再看图,如果左区间已经跑到了i位置,那么就可以返回这个值了,所以只要求出左区间右端点就可以求出最终结果的下标了。
1.求出每次的mid,如果落在左区间,left = mid;
2.求出每次的mid,如果落在右区间,right = mid - 1;
细节:
1.因为这题求的是区间的右端点,所以求中点的方法是:mid = left + (right - left + 1) /2
原因在:在做题中学习(49):排序数组中查找元素的第一个和最后一个位置-CSDN博客
有详细说明
class Solution
{
public:
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-1]<arr[mid])
left = mid;
else
right = mid - 1;
}
return left;
}
};