1095. Find in Mountain Array

Difficulty:
Related Topics:
Similar Questions:

Problem

**(This problem is an **interactive problem.)

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

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:

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:

Solution

/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * function MountainArray() {
 *     @param {number} index
 *     @return {number}
 *     this.get = function(index) {
 *         ...
 *     };
 *
 *     @return {number}
 *     this.length = function() {
 *         ...
 *     };
 * };
 */

/**
 * @param {number} target
 * @param {MountainArray} mountainArr
 * @return {number}
 */
var findInMountainArray = function(target, mountainArr) {
     var maxIndex = findMaxIndex(mountainArr);
     var leftIndex = findInLeft(target, mountainArr, maxIndex);
     if (leftIndex !== -1) return leftIndex;
     return findInRight(target, mountainArr, maxIndex);
};

var findMaxIndex = function(mountainArr) {
    var left = 0;
    var right = mountainArr.length() - 1;
    while (left < right) {
        var mid = left + Math.floor((right - left) / 2);
        if (mountainArr.get(mid) > mountainArr.get(mid + 1)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
};

var findInLeft = function(target, mountainArr, maxIndex) {
    var left = 0;
    var right = maxIndex;
    while (left <= right) {
        var mid = left + Math.floor((right - left) / 2);
        var midVal = mountainArr.get(mid);
        if (midVal === target) {
            return mid;
        } else if (midVal > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
};

var findInRight = function(target, mountainArr, maxIndex) {
    var left = maxIndex;
    var right = mountainArr.length() - 1;
    while (left <= right) {
        var mid = left + Math.floor((right - left) / 2);
        var midVal = mountainArr.get(mid);
        if (midVal === target) {
            return mid;
        } else if (midVal < target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
};

Explain:

nope.

Complexity: