//问题：找极大值元素（返回任意一个极大值均可）
/*
方法一：找最大值一定是极大值
O(n)
*/
class Solution
{
public:
int findPeakElement(vector<int>& nums)
{
int n = nums.size();
if(n==0) return -1; //为空时，返回-1
int max_index = 0;
for(int i = 0; i < n; i++)//找序列中的最大值，一定是极大值
{
if(nums[i]>nums[max_index]) max_index = i;
}
return max_index;
}
};
/*掌握
方法二：借助二分查找思路
right指的数比后一个数大，left指的数比前一个数大，当两个“指针”相遇时，就可以满足极大值条件（两个指针按二分跨度走，故效率较高）
有点像lower_bound函数
O(logn)
*/
class Solution
{
public:
int findPeakElement(vector<int>& nums)
{
if(nums.empty() return -1; //为空时，返回-1
int left = 0,right = nums.size()-1;
while(left<right) //left = right时退出循环，结果是left,right,mid均指向极大值位置
{
int mid = (left+right)/2;
if(nums[mid] < nums[mid+1]) //如果中间值比右边值小，说明峰值在右边
left = mid+1;
else //如果中间值比右边值大，说明峰值在左边（包括a[mid]，故取right=mid）
right = mid;
}
return right;
}
};
