162 Find Peak Element

Leetcode

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.

要求在 log n 时间复杂度完成，如果从左往右遍历，最坏情况时 o(n) 。由于两端都是负无穷，使用二分法，如果中间值的左边比它大，则它左边一定存在一个峰值，有指针移到中间元素。同样，如果右边比它大，它右边一定存在峰值，左指针移到中间元素。如果两边都比它小，它就是峰值。当左右指针相差 2 或以上的时候，不存在数组越界问题。而当左右指针相差 1 的时候左右中大的元素为峰值。

 public int findPeakElement(int[] nums) {
    int left=0, right=nums.length-1;
    int mid;
    while(left+1<right){
        mid=(left+right)>>1;
        if(nums[mid]<nums[mid+1]){
            left=mid;
        } else if(nums[mid]<nums[mid-1]){
            right=mid;
        } else {
            return mid;
        }
    }
    return nums[left]>nums[right]?left:right;
}