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.
分析
找出数组中的一个peak元素，即比相邻的两个元素要大，而且数组两段看做无穷小。
一个简单方法是依次判断是否是peak，如果是的话直接返回，如果不是，说明整个数组是递增或递减的，然后输出首值或末值即可，但这种复杂度为O(n)。
int findPeakElement(int* nums, int numsSize) {
for(int i=1;i<numsSize-1;i++)
{
if(nums[i]>nums[i-1]&&nums[i]>nums[i+1])
return i;
}
if(nums[0]<nums[1])
return numsSize-1;
else
return 0;
}
使用二分法可以达到复杂度为O(log(n))，需要设计好思路。
如果中间值比其后面的值大，则在左边继续寻找，如果中间值比后面的值小，则在右边继续寻找，最后剩下的一个值即为peak.示例代码如下：
public class Solution {
public int findPeakElement(int[] nums) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = (l + r) / 2;
if (nums[mid] > nums[mid + 1])
r = mid;
else
l = mid + 1;
}
return l;
}
}
