Description

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

Given an input array nums, where nums[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 that nums[-1] = nums[n] = -∞.

Example

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:
             1)index number 1 where the peak element is 2
             2)index number 5 where the peak element is 6

Solving

It’s not necessary to compare the left one is smaller or not, cuz nums[-1] and nums[nums.length] could be Integer.MIN_VALUE. So it’s also must has one peak at least in an array.

There are two method to solve this problem.

• 1. Traverse the whole array in sequence, finding the first one who is bigger than its next one and return its index.
• 2. Cuz we only have to find one peak, binary search is enough. Recursion is needed. When we meet the mid number who is bigger than its next one, we search the left part first. Otherwise, searching the right part.

class Solution {
    public int findPeakElement(int[] nums) {
        // method 1: linear complexity
        // for (int i = 0; i < nums.length - 1; i ++)
            // if (nums[i] > nums[i + 1])
                // return i;
        // return nums.length - 1;
        
        // method 2: Binary search
        return binarySearch(nums, 0, nums.length - 1);
    }
    
    private int binarySearch(int[] nums, int left, int right) {
        if (left == right)
            return left;
        // Avoiding overflow
        int mid = left + (right - left) / 2;
        
        // Cuz only need one peak.
        if (nums[mid] > nums[mid + 1])
            return binarySearch(nums, left, mid);
        return binarySearch(nums, mid + 1, right);
    }
}