# LeetCode 1095: Find in Mountain Array

## Problem Restatement

A mountain array increases to a peak and then decreases. We have access only through a `MountainArray.get(index)` API.

We need to find the minimum index where `mountainArr.get(index) == target`. Return `-1` if not found.

We may call `MountainArray.get()` at most `100` times.

The official constraints state that `3 <= mountainArr.length() <= 10^4` and all values are distinct.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `MountainArray` object and `target` integer |
| Output | Minimum index of `target`, or `-1` |

Function shape:

```python
def findInMountainArray(target: int, mountain_arr: 'MountainArray') -> int:
    ...
```

## Key Insight

Three binary searches:

1. Find the peak index.
2. Binary search the ascending left side for `target`.
3. If not found, binary search the descending right side for `target`.
4. Return the smaller index (prefer the left side result).

## Algorithm

**Find peak**: binary search for the index where `get(mid) > get(mid+1)`.

**Search ascending**: standard binary search.

**Search descending**: binary search where the comparison is reversed.

## Correctness

The peak divides the array into an ascending and descending half. Binary search on each half correctly finds the target (if present) with O(log n) queries each.

Total queries: 3 * O(log n) ≤ 3 * 14 = 42, well within 100.

## Edge Cases

- Check the smallest and largest valid search values; off-by-one errors usually appear at the boundaries.
- Decide whether the predicate is looking for the first true value, the last true value, or an exact match.
- When the target is absent, the loop should still terminate and return the problem-specific failure value.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(log n)` API calls | Three binary searches |
| Space | `O(1)` | Constant variables |

## Common Pitfalls

- Do not mix inclusive and half-open bounds inside the same loop.
- Make sure each branch strictly reduces the search interval.

## Implementation

```python
class Solution:
    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
        n = mountain_arr.length()

        lo, hi = 0, n - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):
                lo = mid + 1
            else:
                hi = mid
        peak = lo

        lo, hi = 0, peak
        while lo <= hi:
            mid = (lo + hi) // 2
            val = mountain_arr.get(mid)
            if val == target:
                return mid
            elif val < target:
                lo = mid + 1
            else:
                hi = mid - 1

        lo, hi = peak, n - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            val = mountain_arr.get(mid)
            if val == target:
                return mid
            elif val > target:
                lo = mid + 1
            else:
                hi = mid - 1

        return -1
```

## Testing

```python
class MountainArray:
    def __init__(self, arr): self.arr = arr
    def get(self, index): return self.arr[index]
    def length(self): return len(self.arr)

def run_tests():
    s = Solution()

    assert s.findInMountainArray(3, MountainArray([1,2,3,4,5,3,1])) == 2
    assert s.findInMountainArray(3, MountainArray([0,1,2,4,2,1])) == -1
    assert s.findInMountainArray(1, MountainArray([1,2,3,4,5,3,1])) == 0

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| Target on ascending side | `2` | Minimum index is on the left |
| Target not in array | `-1` | `3` does not appear in `[0,1,2,4,2,1]` |
| Target not in array | `-1` | `3` not in `[0,1,2,4,2,1]` |
| Target at start | `0` | Leftmost occurrence |