0162. Find Peak Element

---

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

Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞.

You must write an algorithm that runs in O(log n) time.

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: 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.

Constraints:

• 1 <= nums.length <= 1000
• -2^31 <= nums[i] <= 2^31 - 1
• nums[i] != nums[i + 1] for all valid i.

---

解法1

二分.

如果有多个结果, 返回其中一个就可以了, 所以当当前值不是peak的时候, 往任意一个比它大的方向搜索就可以了.

class Solution {
    public int findPeakElement(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }
    
    private int helper(int[] nums, int left, int right){
        int mid = (left + right) / 2;
        if((mid == 0 || nums[mid] > nums[mid - 1]) &&(mid == nums.length - 1 || nums[mid] > nums[mid + 1]))
            return mid;
        
        if(mid > 0 && nums[mid] < nums[mid - 1])
            return helper(nums, left, mid - 1);
        
        return helper(nums, mid + 1, right);
    }
}