BM19 寻找峰值

给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。

    public int findPeakElement (int[] nums) {
        // write code here
        if (nums == null || nums.length == 0){
            return -1;
        }
        
        int i = 0;
        
        while (i <= nums.length - 1){
            boolean left = false;
            boolean right = false;
            if (i - 1 < 0 || nums[i] > nums[i-1]){
                left = true;
            }
            if (i + 1 > nums.length - 1 || nums[i] > nums[i+1]){
                right = true;
            }
            if (left && right){
                return i;
            }
            i++;
        }
        
        return -1;
    }

注：直接判断nums[i] > nums[i-1] && nums[i] > nums[i+1]可能会漏掉只有一个或两个的情形。 

附加条件：

1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于

2.假设 nums[-1] = nums[n] = −∞

3.对于所有有效的 i 都有 nums[i] != nums[i + 1]

4.你可以使用O(logN)的时间复杂度实现此问题吗？

使用二分法查找的原理是：

利用二分法，若存在某一位置nums[i] < nums[i+1]时，则继续向右查找，右侧必定有极值。

（因为左侧mid~mid+1已经完成了一次升序，那么，右侧只要有一个降序，就出现了极值，若右侧是下图绿色的值，那么mid+1就是极值，如果是红色的，继续向右查找，最迟直到最后一个元素，必然是极限值，为啥？一直向右找，说明左侧递增，而nums[n] = −∞，所以必然满足）左侧同理。

 

    public int findPeakElement (int[] nums) {
        // write code here
        if (nums == null || nums.length == 0){
            return -1;
        }
        
        int low = 0;
        int high = nums.length - 1;
        while (low < high){
            int mid = low + (high - low) / 2;
            if (nums[mid] < nums[mid + 1]){
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        
        return low;
    }