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.click to show spoilers.Note:Your solution should be in logarithmic complexity.

这道题还是有点麻烦的，要求O(logN)的时间复杂度，想到用二分查找。如果中间元素大于其相邻后续元素，则中间元素左侧(包含该中间元素）必包含一个局部最大值。如果中间元素小于其相邻后续元素，则中间元素右侧必包含一个局部最大值。直到最后左边沿与右边沿相遇

这里有几点要说明：

1. 这里之所以选择只进行中间元素mid跟其相邻后续元素mid+1的大小讨论，而不涉及前一个元素mid-1，主要是方便。mid=(left+right)/2, 这个除法有一个floor效果在里面，即⌊(left+right)/2⌋。这样导致left和right不等时，index为mid和mid+1都存在，但是mid-1有可能小于0。这样每次当mid==0时，mid-1的元素都得特别讨论，麻烦。举个例子，比如left==0, right==1, mid==0, mid-1==-1, mid+1==1，不想讨论mid-1这种情况

2. 如果中间元素大于其相邻后续元素，说明中间元素左侧(包含该中间元素）必包含一个局部最大值，这时候中间元素是可能是局部最大点的，所以移动r = mid而不是r = mid-1; 而如果中间元素小于其相邻后续元素，则中间元素右侧必包含一个局部最大值。这时中间元素肯定不会是局部最大点，所以移动l = mid + 1

3. 之所以要用左右边沿相遇作为找到条件，主要也是不想涉及到mid-1的问题。否则条件是num[mid]>num[mid+1] && num[mid]>num[mid-1]又要分情况mid==0了

4. 如果mid是一个valley, 比如[1, 2, 1, 6, 7], 这时候不知道该往哪边跳？这时候其实往左往右跳都可以。随便指定一个方向都可以，要么往左找到2，要么往右找到7（根据定义它也是peak value）。 因为只用找出一个，所以还是O(logN)

1 public class Solution { 2     public int findPeakElement(int[] num) { 3         int l = 0; 4         int r = num.length - 1; 5         while (l <= r) { 6             if (l == r) return l; 7             int mid = (l + r)/2; 8             if (num[mid] < num[mid+1]) { 9                 l = mid + 1;10             }11             else {12                 r = mid;13             }14         }15         return -1;16     }17 }

(推荐方法)网上另一种老老实实比较mid跟前后元素大小关系的做法：

1 public int findPeakElement(int[] num) { 2     int n = num.length; 3     if (n <= 1) return 0; 4     // handle the first and last element in num[] 5     if (num[0] > num[1]) return 0; 6     if (num[n - 1] > num[n - 2]) return n - 1; 7     int left = 1, right = n - 2; 8     while (left <= right) { 9         int mid = (left + right) >> 1;10         if (num[mid] > num[mid - 1] && num[mid] > num[mid + 1]) {11             return mid;12         } else if (num[mid] > num[mid + 1]) {13             right = mid - 1;14         } else {15             left = mid + 1;16         }17     }18     return -1;19 }