162. Find Peak Element

Problem

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 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 either index number 1 where the peak element is 2, 
             or index number 5 where the peak element is 6.

Note:

Your solution should be in logarithmic complexity.

Problem Summary

A peak element is an element whose value is greater than the values of its left and right 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, returning the position of any peak is fine. You may assume that nums[-1] = nums[n] = -∞.

Note:

• Your solution should have O(logN) time complexity.

Solution Approach

• Given an array that contains multiple "peaks" (a peak is defined as an index i whose element is greater than the elements at positions i-1 and i+1), find this "peak" and output the index of any one peak.
• This problem is a pseudo-enhanced version of problem 852. In problem 852, there is only one peak, while in this problem there may be multiple peaks. But in fact the search code is the same, because this problem only requires outputting the index of any peak. The approach is the same as problem 852.

Code

package leetcode

// Solution 1: Binary search
func findPeakElement(nums []int) int {
	if len(nums) == 0 || len(nums) == 1 {
		return 0
	}
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + (high-low)>>1
		if (mid == len(nums)-1 && nums[mid-1] < nums[mid]) || (mid > 0 && nums[mid-1] < nums[mid] && (mid <= len(nums)-2 && nums[mid+1] < nums[mid])) || (mid == 0 && nums[1] < nums[0]) {
			return mid
		}
		if mid > 0 && nums[mid-1] < nums[mid] {
			low = mid + 1
		}
		if mid > 0 && nums[mid-1] > nums[mid] {
			high = mid - 1
		}
		if mid == low {
			low++
		}
		if mid == high {
			high--
		}
	}
	return -1
}

// Solution 2: Binary search
func findPeakElement1(nums []int) int {
	low, high := 0, len(nums)-1
	for low < high {
		mid := low + (high-low)>>1
		// If mid is larger, then a peak exists on the left, high = m; if mid + 1 is larger, then a peak exists on the right, low = mid + 1
		if nums[mid] > nums[mid+1] {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low
}