530. Find in Mountain Array

A mountain array strictly increases to a single peak and then strictly decreases. Given such an array and a target, return the smallest index whose value equals the target, or -1 if absent. Use binary search: first find the peak, then search each side. Input: '[arr], target'.

Input: '[arr], target'.

Output: Integer — the smallest matching index, or -1.

Examples

Input: [1,2,3,4,5,3,1], 3
Output: 2
Explanation: 3 first appears at index 2.

Input: [1,5,2], 5
Output: 1
Explanation: Peak value.

Input: [0,5,3,1], 4
Output: -1
Explanation: 4 is absent.

Constraints

• 3<=n<=10^4
• values form a mountain

Asked by