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.

題意：尋找一個給定數(shù)組的峰值，峰值有可能存在于波峰上，也可能這個數(shù)組是遞增或遞減的，峰值存在于起始或結(jié)束。

思路：
用二分法查找middle，如果middle值比兩邊的值都大，那么middle就是peak；如果middle處于上坡，那么舍棄middle左側(cè)；如果middle處于下坡或波底，都可以舍棄右側(cè)。
如果跳出循環(huán)扔沒有找到peak，那么此時left和right時臨接的，返回left和right中的較大值就是指定區(qū)間的peak。

bug:
第一遍做的時候，以為給定數(shù)組肯定會存在一個波峰，忽略了只有升序或降序的case

public int findPeakElement(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int peak = -1;
    int left = 0, right = nums.length - 1;
    while (left + 1 < right) {
        int middle = left + (right - left) / 2;
        if (nums[middle] > nums[middle - 1] && nums[middle] > nums[middle + 1]) {
            return middle;
        } else if (nums[middle] > nums[middle - 1] && nums[middle] < nums[middle + 1]) {
            left = middle;
        } else {
            right = middle;
        }
    }

    return nums[left] > nums[right] ? left : right;
}