题目链接：Find Peak Element
A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[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 num[-1] = num[n] = -∞.
For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.
Note:
Your solution should be in logarithmic complexity.
这道题的要求是找出数组中的峰值元素，返回其下标。其中峰值元素是指该元素大于相邻元素（num[-1] = num[n] = -∞），而且数组中相邻元素无重复。如果有多个峰值，返回任意一个即可。而且要求对O(logn)杂度。
直接思路就是遍历一边数组，不过这样复杂度是O(n)。至于要达到O(logn)，就首先想到二分了。找到中间元素nums[m]，可以与两边元素比较，如果nums[m]大于两边的，那nums[m]就直接是峰值了；否则，选取大于nums[m]的一侧接着二分即可。由于每次会选出左侧或者右侧，因此无需与两侧元素都进行比较，只需要比较一侧即可（这里选择与nums[m]的右侧元素nums[m+1]进行比较）。
具体做法：取数组左右端点l和r，然后令中值m1等于(l+r)/2，m2等于m1+1，这样比较nums[m1]和nums[m2]的大小：
- 如果nums[m1]小于nums[m2]，那么说明nums[m1]肯定不可能是峰值，而m1的右侧一定存在峰值，因为如果nums[m2]大于nums[m2+1]，那么m2处就是峰值，否则nums[m2+1]可能就是峰值（如果大于nums[m2+2]的话），以此类推，可以确定这部分一定存在峰值。因此可以令l等于m2，接着进行二分搜索。
- 如果nums[m1]大于nums[m2]，那么说明nums[m2]肯定不可能是峰值，而m2的左侧一定存在峰值，理由同上。因此可以令r等于m1，接着进行二分搜索。
最后l等于r时结束，返回l即可。
时间复杂度：O(logn)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution
{
public:
int findPeakElement(vector<int>& nums)
{
int l = 0, r = nums.size() - 1;
while(l < r)
{
int m1 = (l + r) / 2, m2 = m1 + 1;
if(nums[m1] < nums[m2])
l = m2;
else
r = m1;
}
return l;
}
};