## Algorithm

Problem Name: 1095. Find in Mountain Array

(This problem is an interactive problem.)

You may recall that an array `arr` is a mountain array if and only if:

• `arr.length >= 3`
• There exists some `i` with `0 < i < arr.length - 1` such that:
• `arr[0] < arr[1] < ... < arr[i - 1] < arr[i]`
• `arr[i] > arr[i + 1] > ... > arr[arr.length - 1]`

Given a mountain array `mountainArr`, return the minimum `index` such that `mountainArr.get(index) == target`. If such an `index` does not exist, return `-1`.

You cannot access the mountain array directly. You may only access the array using a `MountainArray` interface:

• `MountainArray.get(k)` returns the element of the array at index `k` (0-indexed).
• `MountainArray.length()` returns the length of the array.

Submissions making more than `100` calls to `MountainArray.get` will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

Example 1:

```Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.```

Example 2:

```Input: array = [0,1,2,4,2,1], target = 3
Output: -1
Explanation: 3 does not exist in `the array,` so we return -1.```

Constraints:

• `3 <= mountain_arr.length() <= 104`
• `0 <= target <= 109`
• `0 <= mountain_arr.get(index) <= 109`

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const findInMountainArray = function(target, mountainArr) {
const p = findPeak(mountainArr)
if (mountainArr.get(p) === target) {
return p
}
const left = binarySeach(mountainArr, 0, p, target, 'asc')
if (left > -1) {
return left
}
return binarySeach(mountainArr, p + 1, mountainArr.length(), target, 'dsc')
}

function findPeak(arr) {
let left = 0
let right = arr.length()
while (left < right) {
const mid = Math.floor((left + right) / 2)
if (arr.get(mid) < arr.get(mid + 1)) {
left = mid + 1
} else {
right = mid
}
}
return left
}

function binarySeach(mountainArr, start, end, target, order) {
let left = start
let right = end
while (left < right) {
const mid = Math.floor((left + right) / 2)
if (target === mountainArr.get(mid)) {
return mid
} else if (
(target > mountainArr.get(mid) && order === 'asc') ||
(target < mountainArr.get(mid) && order === 'dsc')
) {
left = mid + 1
} else {
right = mid
}
}
return -1
}
``````
Copy The Code &

Input

cmd
array = [1,2,3,4,5,3,1], target = 3

Output

cmd
2

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
#class MountainArray:
#    def get(self, index: int) -> int:
#    def length(self) -> int:

class Solution:
def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
l, r = 0, mountain_arr.length() - 1
while l <= r:
mid = (l  + r) // 2
md = mountain_arr.get(mid)
if mid and mountain_arr.get(mid - 1) < md > mountain_arr.get(mid + 1):
pivot = mid
break
elif md < mountain_arr.get(mid + 1):
l = mid + 1
else:
r = mid - 1
l, r = 0, pivot
while l <= r:
mid = (l + r) // 2
md = mountain_arr.get(mid)
if md == target:
return mid
elif md < target:
l = mid + 1
else:
r = mid - 1
l, r = pivot, mountain_arr.length() - 1
while l <= r:
mid = (l + r) // 2
md = mountain_arr.get(mid)
if md == target:
return mid
elif md > target:
l = mid + 1
else:
r = mid - 1
return -1

``````
Copy The Code &

Input

cmd
array = [1,2,3,4,5,3,1], target = 3

Output

cmd
2