題目鏈接
tag:
- Medium；
question：
??A peak element is an element that is greater than its neighbors.
Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that nums[-1] = nums[n] = -∞.
Example 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.
Note:Your solution should be in logarithmic complexity.
思路：
??題目中提示了要用對數(shù)級的時間復雜度躺坟，那么我們就要考慮使用類似于二分查找法來縮短時間，由于只是需要找到任意一個峰值，那么我們在確定二分查找折半后中間那個元素后，和緊跟的那個元素比較下大小蜂林，如果大于，則說明峰值在前面拇泣，如果小于則在后面噪叙。這樣就可以找到一個峰值了，代碼如下：
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[mid + 1]) left = mid + 1;
else right = mid;
}
return right;
}
};
