Find in Mountain Array

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:

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

2.MountainArray.length() returns the length of the array.

Example :

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.

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

class MountainArray
{
public:
    vector<int> arr;
    MountainArray(vector<int> &arr)
    {
        this->arr = arr;
    }
    int length()
    {
        return arr.size();
    }
    int get(int index)
    {
        return arr[index];
    }
};
int findMountain(MountainArray mountainArr, int low, int high)
{
    int mid = (low + high) / 2;
    if ((mountainArr.get(mid) > mountainArr.get(mid - 1))
     && (mountainArr.get(mid) > mountainArr.get(mid + 1)))
        return mid;
    else if ((mountainArr.get(mid + 1) > mountainArr.get(mid)))
        return findMountain(mountainArr, mid, high);
    return findMountain(mountainArr, low, mid);
}
int findInMountainLeft(int target, MountainArray
    &mountainArr, int low, int high)
{
    if (high < low)
        return -1;
    if (high == low)
        if (mountainArr.get(high) == target)
            return high;
    if (high == low + 1)
    {
        if (mountainArr.get(low) == target)
            return low;
        if (mountainArr.get(high) == target)
        {
            return high;
        }
        return -1;
    }
    int mid = (low + high) / 2;

    if (mountainArr.get(mid) == target)
        return mid;
    else if (mountainArr.get(mid) > target)
        return findInMountainLeft(target, mountainArr, 
        low, mid - 1);
    return findInMountainLeft(target, mountainArr, 
         mid + 1, high);
}
int findInMountainRight(int target, MountainArray 
    &mountainArr, int low, int high)
{

    if (high < low)
        return -1;
    if (high == low)
        if (mountainArr.get(high) == target)
            return high;
    if (high == low + 1)
    {
        if (mountainArr.get(low) == target)
            return low;
        if (mountainArr.get(high) == target)
        {
            return high;
        }
        return -1;
    }
    int mid = (low + high) / 2;

    if (mountainArr.get(mid) == target)
        return mid;
    else if (mountainArr.get(mid) < target)
        return findInMountainRight(target, mountainArr,
                   low, mid - 1);
    return findInMountainRight(target, mountainArr, mid + 1, 
         high);
}
int findInMountainArray(int target, MountainArray &mountainArr)
{
    int high = mountainArr.length() - 1;
    int low = 0;
    int mntIdx = findMountain(mountainArr, low, high);

    int isInLeftIdx = findInMountainLeft(target, 
                 mountainArr, low, mntIdx);

    if (-1 == isInLeftIdx)
        return findInMountainRight(target, mountainArr, 
        mntIdx, high);
    return isInLeftIdx;
}

int main()
{
    vector<int> array = {1, 2, 3, 4, 5, 3, 1};
    int target = 3;

    MountainArray mountarray(array);

    cout << findInMountainArray(target, mountarray);

    return 0;
}