162. Find Peak Element

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.

Note:

Your solution should be in logarithmic complexity.

Solution:

The problem description indicates we can imagine nums[-1] and nums[n] are -INF. That is to say there must be at least one peak in the array.

Therefore, we use binary search to find any peak in the array.

If in any point, we find it is less than its right. We know there must be a peak to the right.

Otherwise, we know there must be a peak to the left.

The time complexity is O(logn).



Code:

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