Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input arraynums, wherenums[i] ≠ nums[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 thatnums[-1] = nums[n] = -∞.

Example 1:

Input:
nums
 = 
[1,2,3,1]
Output:
 2

Explanation:
 3 is a peak element and your function should return the index number 2.

Example 2:

Input:
nums
 = 
[
1,2,1,3,5,6,4]

Output:
 1 or 5 

Explanation:
 Your function can return either index number 1 where the peak element is 2, 
             or index number 5 where the peak element is 6.

Note:

Your solution should be in logarithmic complexity.

Analysis

乍一看此题中的数列并没有sorted过，是不是就不能用binary search了呢？

其实binary search最基本的特征其实在于根据判断条件，每次减半搜索空间（search space）。这里其实也可以，在于nums[mid]可以与nums[mid+1]比较大小，以此判断在上升趋势还是下降趋势，从而改变搜索边界。最终得到的index就（可能，取决于用哪个template）是局部的peak。

Solution

Template #3

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left + 1< right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                // descending
                right = mid;
            } else {
                // ascending
                left = mid;
            }
        }
        if (nums[left] >= nums[right]) {
            return left;
        }
        return right;

    }
}

Template #2

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                // descending
                right = mid;
            } else {
                // ascending
                left = mid + 1;
            }
        }
        return left;
    }
}