峰值元素是指其值大於左右相鄰值的元素。
給定一個輸入陣列 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素並返回其索引。
陣列可能包含多個峰值，在這種情況下，返回任何一個峰值所在位置即可。
你可以假設 nums[-1] = nums[n] = -∞。
範例 1:
輸入: nums = [1,2,3,1]
輸出: 2
解釋: 3 是峰值元素，你的函數應該返回其索引 2。
範例 2:
輸入: nums = [1,2,1,3,5,6,4]
輸出: 1 或 5
解釋: 你的函數可以返回索引 1，其峰值元素為 2；
或者返回索引 5， 其峰值元素為 6。
說明:
你的解法應該是 O(logN) 時間複雜度的。
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int left=0;
int right=nums.size()-1;
int mid;
if(nums.size()==1||(nums.size()==2&&nums[0]>nums[1]))
return 0;
if(nums.size()==2&&nums[0]<nums[1])
return 1;
while(left<=right)
{
mid=(left+right)/2;
if(mid!=0&&mid!=(nums.size()-1))
{
if(nums[mid]>nums[mid-1]&&nums[mid]>nums[mid+1])
return mid;
else if(nums[mid]>nums[mid-1]&&nums[mid]<nums[mid+1])
left=mid+1;
else if(nums[mid]<nums[mid-1]&&nums[mid]>nums[mid+1])
right=mid-1;
else
{
if(nums[mid-1]>nums[mid+1])
right=mid-1;
else
left=mid+1;
}
}
if(mid==0||mid==(nums.size()-1))
break;
}
mid=max_element(nums.begin(),nums.end())-nums.begin();
return mid;
}
};
這道題目，剛開始看到時間複雜度為O(logn)我就知道應該是用二分法。但是想了很久也沒想清楚怎麼用二分法。之後看了別人的題解，才發現自己漏掉了最重要的一個條件nums[-1] = nums[n] = -∞。這個條件的含義就是，這個輸入陣列的最左邊和最右邊的數位都是無窮小的。那麼每次在二分的時候，如果二分位置的數位不是最大的，那就說明要繼續二分，之後尋找左右兩邊數位較大的位置作為下一個二分割區間的一個邊界（這裡就是最難理解的，因為陣列最左側和最右側都是無窮小的，所以新的二分割區間不可能會一直遞增，中間必定會有遞減的部分，所以必定存在峰值）。
記錄這道題，之後再來做，下次一定不要糾結太多了。