> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/binary-search/bs-on-1d-array/1095.-find-in-mountain-array.md).

# 1095. Find in Mountain Array

## Problem Statement

<br>

*(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.

&#x20;

**Example 1:**

<pre><code><strong>Input: array = [1,2,3,4,5,3,1], target = 3
</strong><strong>Output: 2
</strong><strong>Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: array = [0,1,2,4,2,1], target = 3
</strong><strong>Output: -1
</strong><strong>Explanation: 3 does not exist in the array, so we return -1.
</strong></code></pre>

&#x20;

**Constraints:**

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

## Intuition

```
Approach:

Find the peak and do Binary search on both sides

Only one edge case
While finding peak,
3 5 4 3 2

let
3 5 4 3 2
l h
m 

3 < 3 < 5 is false, so we will not be able to judge the increasing and decreasing 
side so 
it goes in else, high = mid-1
returns -1

hence finding at index -1, gives error in == target statement


so, here there is confirm peak element 
so we search peak in the range 1 to len-2 to avoid this
```

### Links

<https://leetcode.com/problems/find-in-mountain-array/description/?envType=daily-question&envId=2023-10-12>

### Video Links

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int find_peak(int low, int high, MountainArray &arr){
        while(low<=high){
            int mid = low+(high-low)/2;
            int num = arr.get(mid);
            if(arr.get(mid-1) < num and num > arr.get(mid+1) )
                return mid;
            else if(arr.get(mid-1) < num and num < arr.get(mid+1))
                low = mid+1;
            else
                high = mid-1;
        }

        return -1;
    }

    int binary_search(int low, int high, MountainArray &arr, int target, bool check){
        while(low<=high){
            int mid = low + (high-low)/2;
            int num = arr.get(mid);

            if(num == target)
                return mid;
            else if(num > target){
                if(check)
                    high = mid-1;
                else
                    low = mid+1;
            }
            else{
                if(check)
                    low = mid+1;    
                else
                    high = mid-1;
            }
        }

        return -1;
    }

    
    int findInMountainArray(int target, MountainArray &arr) {
        int len = arr.length();
        int peak = find_peak(1, len-2, arr);

        if(arr.get(peak) == target)
            return peak;

        int left = binary_search(0, peak-1, arr, target, true);
        int right = binary_search(peak+1, len-1, arr, target, false);

        if(left == -1 and right == -1)
            return -1;
        else if(left != -1 and right != -1)
            return min(left, right);

        return max(left, right);
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###