162 Find Peak Element

162. Find Peak Element

1. Question

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

Given an input array wherenum[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 thatnum[-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.

2. Implementation

(1) Binary Search

class Solution {
    public int findPeakElement(int[] nums) {
        if (nums.length <= 1) {
            return 0;
        }

        int start = 0, end = nums.length - 1, mid = 0;

        while (start + 1 < end) {
            mid = start + (end - start) / 2;

            if (nums[mid - 1] < nums[mid] && nums[mid] > nums[mid + 1]) {
                return mid;
            }
            else if (nums[mid - 1] < nums[mid] && nums[mid] < nums[mid + 1]) {
                start = mid + 1;
            }
            else {
                end = mid - 1;
            }
        }

        return nums[start] > nums[end] ? start : end;
    }
}

3. Time & Space Complexity

Binary Search: 时间复杂度O(logn), 空间复杂度O(1)