852. Peak Index in a Mountain Array

Problem

Let's call an array A a mountain if the following properties hold:

• A.length >= 3
• There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]

Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].

Example 1:

Input: [0,1,0]
Output: 1

Example 2:

Input: [0,2,1,0]
Output: 1

Note:

1. 3 <= A.length <= 10000
2. 0 <= A[i] <= 10^6
3. A is a mountain, as defined above.

Summary

We call an array A that satisfies the following properties a mountain:

• A.length >= 3
• There exists 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1] Given an array that is definitely a mountain, return any value of i that satisfies A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].

Note:

• 3 <= A.length <= 10000
• 0 <= A[i] <= 10^6
• A is a mountain as defined above

Solution Ideas

• Given an array, there exists exactly one "peak" in the array (the definition of a peak is that the element at index i is greater than the elements at positions i-1 and i+1). Find this "peak" and output the index of one peak.
• This problem can be solved directly with binary search. The elements in the array are basically ordered. The condition for determining whether it is a peak is to compare the two numbers on the left and right: if the current number is greater than both the left and right numbers, then the peak has been found. All other cases are on a slope. There are two ways to write this problem: the first is the standard binary search method, and the second is a variant binary search method.

Code

package leetcode

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

// Solution 2: Binary search
func peakIndexInMountainArray1(A []int) int {
	low, high := 0, len(A)-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 A[mid] > A[mid+1] {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low
}