1095. Find in Mountain Array

Practice Find in Mountain Array for free on NudgeCode: Hard, Binary Search pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

A mountain array strictly increases up to a peak and then strictly decreases: its length is at least 3, and there is an index p with 0 < p < length - 1 such that arr[0] < arr[1] < ... < arr[p] and arr[p] > arr[p + 1] > ... > arr[length - 1].

Given a mountain array and a target, return the smallest index i with arr[i] == target, or -1 if target is not in the array.

You can't read the array directly. Use the MountainArray interface:

• mountainArr.get(i) returns the element at index i (0-based)
• mountainArr.length() returns the length

Each test allows at most 100 calls to get; the 101st call fails the test. length() calls are not counted. In the tests mountainArr is shown as the plain array.

Example

target = 3, mountainArr = [1,2,3,4,5,3,1]  ->  2

3 is at index 2 and index 5; the smaller index is 2.

Constraints

• 3 <= mountainArr.length() <= 10^4
• 0 <= target <= 10^9
• 0 <= mountainArr.get(i) <= 10^9