437. Peak Index in a Mountain Array

An array arr is a mountain array if: arr.length >= 3, there exists i (0 < i < len-1) such that arr[0] < arr[1] < ... < arr[i] > arr[i+1] > ... > arr[len-1]. Given a mountain array, return the index i of the peak. Solve in O(log n).

Input: A mountain integer array arr.

Output: The index of the peak element.

Examples

Input: [0,1,0]
Output: 1
Explanation: Peak is at index 1.

Input: [0,2,1,0]
Output: 1
Explanation: Peak value 2 is at index 1.

Input: [1,3,5,4,2]
Output: 2
Explanation: Peak value 5 at index 2.

Constraints

• 3 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^6
• arr is guaranteed to be a mountain array

Asked by