背景与要求:
Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks. nums[-1]=nums[n]=-∞。
给定一个0索引的整数数组nums，查找峰值元素并返回其索引。如果数组包含多个峰值，则返回任意一个峰值的索引。
其中：峰值元素严格大于其相邻元素，元素严格大于数组外的相邻元素(即nums[-1]=nums[n]=-∞)，算法的时间复杂度需要是O(log n)。
限制条件:
1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
nums[i] != nums[i + 1] for all valid i.
测试用例1:
Input: nums = [1,2,3,1]
Output: 2
测试用例2:
Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5重点应当在于发现并证明二分查找的应用可以解决此问题，即:
1. 最基础的: 任意数组一定存在至少一个峰值;
2. 任意数组都有方法找到一个mid位置，保证一定有峰值出现在mid的一侧;
3. 通过二分查找每次都可以确定一个mid的位置。
只要能证明上面3点，就可以很快得到算法。
证明主要是通过数学逻辑:
1.1 若数组长度为1，峰值就是该唯一元素(边界外看做负无穷)
1.2 若数组长度大于1，从最左边的nums[0]开始往右查找并判断
1.2.1 若出现nums[i]
2 整理上述推论可知，一个满足nums[i]<(>)nums[i+1]的元素，其右边(左边)一定存在峰值
3 即，通过不断选择mid存在峰值的一端继续运算，可以不断逼近直至找到一个峰值
一旦完成了以上论证，代码本身就是基于二分查找(Binary Search)的框架进行调整。java实现如下:
class Solution {
public int findPeakElement(int[] nums) {
int n = nums.length;
// 检查边界条件
if(nums.length == 1) return 0;
if(nums[0] > nums[1]) return 0;
if(nums[n-1] > nums[n-2]) return n-1;
// 开始二分查找
int start = 1;
int end = n-2;
while(start <= end) {
int mid = start + (end - start)/2;
if(nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1]) return mid;
else if(nums[mid] < nums[mid-1]) end = mid - 1;
else if(nums[mid] < nums[mid+1]) start = mid + 1;
}
return -1;
}
}