合并两个有序数组、第一个错误的版本和搜索旋转排序数组

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3
​
输出: [1,2,2,3,5,6]

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void}
 */
const merge = function (nums1, m, nums2, n) {
  // 暂存 merge 结果
  const result = [];
  // 定义两个指针 j、k，分别指向当前 nums1 与 nums2 数组中正在比较值的数组下标，从前往后
  let j = 0; let k = 0;
  // 遍历 nums1 和 nums2 数组，遍历完一个数组后跳出循环
  while (j < m && k < n) {
    // 比较 nums1 中取的值与 nums2 中取的值，将较小值 push 到结果数组中
    // 并将下标往后加一，下次循环取后一个值进行比较
    if (nums1[j] > nums2[k]) {
      result.push(nums2[k]);
      k++;
    } else {
      result.push(nums1[j]);
      j++;
    }
  }
​
  // nums1 或 nums2 中有一个数组未遍历完全
  if (result.length < m + n) {
    // 如果 nums1 遍历完了，则说明 nums2 未遍历完全，
    // 将 nums2 中剩余未比较的数据直接 push 到 merge 结果数组中
    // 反之亦然
    if (j === m) {
      result.push(...nums2.slice(k, n));
    } else {
      result.push(...nums1.slice(j, m));
    }
  }
  // 清空 nums1，将 merge 结果 push 到 nums1 中
  nums1.splice(0, nums1.length);
  nums1.push(...result);
};

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void}
 */
const merge = function (nums1, m, nums2, n) {
  let currentInsertIndex = nums1.length - 1;
  while (currentInsertIndex >= 0 && n > 0 && m > 0) {
    if (nums1[m - 1] > nums2[n - 1]) {
      nums1[currentInsertIndex--] = nums1[m - 1];
      m--;
    } else {
      nums1[currentInsertIndex--] = nums2[n - 1];
      n--;
    }
  }
​
  // nums2 未遍历完成，将 nums2 中剩余未遍历的数据插入到 nums1 头部
  // nums1 未遍历完成不用关心，已排序好了
  if (n > 0) {
    nums1.splice(0, n, ...nums2.slice(0, n));
  }
};

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void}
 */
const merge = function (nums1, m, nums2, n) {
  // 两数组合并，将 nums1 后面的占位删除并放入 nums2
  nums1.splice(m, n, ...nums2);
  // 排序
  nums1.sort((a, b) => a - b);
};

给定 n = 5，并且 version = 4 是第一个错误的版本。
​
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
​
所以，4 是第一个错误的版本。

const solution = function(isBadVersion) {
  return function firstBadVersion (n) {
    for (let i = 1; i < n; i++) {
      if (isBadVersion(i)) {
        return i;
      }
    }
    return n;
  }
};

const solution = function(isBadVersion) {
  return function firstBadVersion (n) {
    let left = 1;
    let right = n;
    while (left <= right) {
      const mid = Math.floor(left + (right - left) / 2);
      if (isBadVersion(mid)) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

const search = function (nums, target) {
  const min = Math.min.apply(null, nums);
  const max = Math.max.apply(null, nums);
  const len = nums.length;
  let pos;
  let lo;
  let hi;
  let mid;
​
  if (target > nums[len - 1]) {
    pos = nums.indexOf(max);
    lo = 0;
    hi = pos;
  } else {
    pos = nums.indexOf(min);
    lo = pos;
    hi = len - 1;
  }
  while (lo <= hi) {
    mid = Math.ceil((lo + hi) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  return -1;
};

const search = function(nums, target) {
  if(nums.length === 0){
    return -1;
  }
​
  let left = 0;
  let right = nums.length - 1;
  let mid;
​
  while(left <= right){
    mid = parseInt((left + right) / 2);
    if(nums[mid] === target){
      return mid;
    } else if(nums[mid] < nums[right]) {
      if(nums[mid] < target && target <= nums[right]) {
            left = mid + 1;
      } else {
        right = mid - 1;
      }
    } else {
      if(nums[left] <= target && target < nums[mid]){
            right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
  }
  return -1;
};