# 1095. Find in Mountain Array

(This problem is an interactive problem.)

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

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

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

You can’t 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() <= 10000`
• `0 <= target <= 10^9`
• `0 <= mountain_arr.get(index) <= 10^9`

``````class Solution {
public:
int findInMountainArray(int target, MountainArray &mountainArr) {
int n = mountainArr.length(), left = 0, right = n - 1, peak = -1;
while (left < right) {
int mid = left + (right - left) / 2;
if (mountainArr.get(mid) < mountainArr.get(mid + 1)) left = mid + 1;
else right = mid;
}
peak = left;
if (mountainArr.get(peak) == target) return peak;
int idx1 = helper(target, mountainArr, 0, peak - 1, true);
int idx2 = helper(target, mountainArr, peak + 1, n - 1, false);
return idx1 == -1 ? idx2 : idx1;
}
int helper(int target, MountainArray &mountainArr, int left, int right, bool isAsc) {
while (left < right) {
int mid = left + (right - left) / 2, cur = mountainArr.get(mid);
if (cur == target) return mid;
else if (cur < target) {
if (isAsc) left = mid + 1;
else right = mid;
} else {
if (isAsc) right = mid;
else left = mid + 1;
}
}
return mountainArr.get(right) == target ? right : -1;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1095

Longest Mountain in Array

Peak Index in a Mountain Array

Find Minimum in Rotated Sorted Array

Minimum Number of Removals to Make Mountain Array

https://leetcode.com/problems/find-in-mountain-array/

https://leetcode.com/problems/find-in-mountain-array/discuss/317603/C%2B%2B-Find-Peak-(162)-%2B-Binary-Search

https://leetcode.com/problems/find-in-mountain-array/discuss/317607/JavaC%2B%2BPython-Triple-Binary-Search

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation