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 }