1095.山脉数组中查找目标值

链接：1095.山脉数组中查找目标值
难度：Hard
标签：数组、二分查找、交互
简介：给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。

题解 1 - javascript

• 编辑时间：2020-04-29
• 执行用时：64ms
• 内存消耗：34.3MB
• 编程语言：javascript
• 解法介绍：二分查找减少次数。

/**
 * // 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) {
  const data = new Map();
  // 递归搜索，初始化为首位下标
  return search(0, mountainArr.length() - 1);
  function search(left, right) {
    // 如果 长度为负则不存在
    if (left > right) return -1;
    // 如果下标相等则直接判断该值是否为目标
    else if (left === right) return getNum(left) === target ? left : -1;
    const leftNum = getNum(left),
      rightNum = getNum(right);
    if (target < leftNum && target < rightNum) return -1;
    const mid = (right + left) >> 1;
    const midNum = getNum(mid);
    // 如果左右值直接为目标值则返回
    if (target === leftNum) return left;
    if (target === rightNum) return right;
    // 如果中间值为目标值则再次判断左下标到中间值是否存在更小值
    if (target === midNum) {
      if (midNum > leftNum) {
        let index = search(left, mid - 1);
        return index === -1 ? mid : index;
      }
      return mid;
    }
    if (target < leftNum) {
      // 如果目标值小于左值则判断可能出现的一边坡度
      if (target < midNum) return search(mid + 1, right);
      else return search(left, mid - 1);
    } else if (target < rightNum) {
      // 如果目标值小于右值则判断可能出现的一边坡度
      if (target < midNum) return search(left, mid - 1);
      else return search(mid + 1, right);
    } else {
      // 如果目标值大于中值则判断左右值的大小进行划分区域
      if (target > midNum) {
        if (leftNum < rightNum) return search(mid + 1, right);
        else if (leftNum > rightNum) return search(left, mid - 1);
      }
      // 否则分段判断
      let index = search(left, mid - 1);
      if (index === -1) index = search(mid + 1, right);
      return index;
    }
  }
  // 获取值，储存在本地data中减少获取次数
  function getNum(index) {
    let res = data.get(index);
    if (res === undefined) {
      res = mountainArr.get(index);
      data.set(index, res);
    }
    return res;
  }
};