# 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

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/binary-search/bs-on-1d-array/1095.-find-in-mountain-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.