438. Find in Mountain Array (Bitonic Search)

Given a mountain (bitonic) array arr and a target, return the index of target. Return -1 if target is not found. A mountain array strictly increases then strictly decreases. Solve in O(log n).

Input: A mountain integer array arr and integer target.

Output: Index of target, or -1 if not found.

Examples

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

Input: [1,2,3,4,5,3,1], 6
Output: -1
Explanation: 6 not present.

Input: [0,5,4,3,2,1], 5
Output: 1
Explanation: 5 found at index 1 (peak).

Constraints

• 3 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^6
• arr is a valid mountain array
• All values distinct

Asked by