合并两个有序数组

题目

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

求解

https://leetcode.cn/problems/median-of-two-sorted-arrays/solutions/258842/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
  // 保证nums1的较短数组
  if (nums1.length > nums2.length) {
    [nums1, nums2] = [nums2, nums1];
  }
  //m为较短数组的长度,n为较长数组的长度
  let m = nums1.length; // Add missing variable declaration for m
  let n = nums2.length; // Add missing variable declaration for n
  // 左边元素的个数
  let totalLeft = Math.floor((m + n + 1) / 2);
  // 在nums1的[0,m]中找合适的分割线
  // 使得nums1[i-1] <= nums2[j] && nums2[j-1] <= nums1[i]
  let left = 0, right = m;
  // 二分查找
  while(left < right){ // Fix the loop condition
    let i = left + Math.floor((right - left + 1) / 2);
    let j = totalLeft - i;
    if(nums1[i-1] > nums2[j]){
      //下一轮搜索区间在[left,i-1]
      right = i-1;
    }
    else{
      //下一轮搜索区间在[i,right],注意当这个区间只有两个元素时，会陷入死循环，因此在二分的时候要+1
      left = i
    }
  }
  //退出循环后找到了想要的分割线
  let i = left;
  let j = totalLeft - i;
  // 定义左右两边的四个值,还是为了适应特殊情况
  // 如果 i 等于 0，说明 nums1 的左侧没有元素，所以左侧最大值设为负无穷 -Infinity。否则，左侧最大值就是 nums1[i-1]。
  //左侧找最大值，右侧找最小值
  let nums1LeftMax = i === 0 ? -Infinity : nums1[i-1];
  let nums1RightMin = i === m ? Infinity : nums1[i];
  let nums2LeftMax = j === 0 ? -Infinity : nums2[j-1];
  let nums2RightMin = j === n ? Infinity : nums2[j];
  // 如果总长度是奇数
  if((m + n) % 2 === 1){
    return Math.max(nums1LeftMax, nums2LeftMax);
  }
  else{
    return (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2;
  }
};

二分查找

一看就会，一写就废。问题出在边界无法掌握，一不小心就死循环了，因此要掌握二分查找的边界
https://blog.csdn.net/qq_45978890/article/details/116094046

二分查找的条件

• 有序
• 只找一个

二分查找的边界

• 1、[左闭，右闭]

  const search1 = (arr, target) => {
    let left = 0, right = arr.length - 1;
    // 二分查找,闭区间
    while (left <= right) {  // 因为是闭区间，所以left 要小于等于right
      let mid = left + Math.floor((right - left) / 2);
      if (arr[mid] < target) { // 目标值在右边
        left = mid + 1;  //应为是左闭右闭，所以不用担心，边界mid+1后mid+1不能被比较
      }
      else if (arr[mid] > target) { // 目标值在左边
        right = mid - 1;
      } else {
        // 找到目标值
        return mid;
      }
    }
    return -1;
  }
  //犯个错误，第二个else if，我用了if，然后下面用了else，导致第二个if和最后的else成了组合，不再能表示所有情况。
  console.log(search([1,2,3,4,5,6,7,8,9], 5)) // 4

• 2、[左闭，右开)

  const search = (arr, target) => {
    let left = 0, right = arr.length; // 左闭右开区间
    while (left < right) { //终止条件
      let mid = left + Math.floor((right - left) / 2);
      if (arr[mid] < target) { // 目标值在右边
        left = mid + 1; // 更新左边界
      } else if (arr[mid] > target) {  // 目标值在左边
        right = mid; // 更新右边界
      } else {
        return mid;
      }
    }
  }

• 3、(左开，右闭]

  //左开右闭区间
  const search = (arr, target) => {
    let left = -1, right = arr.length - 1; // 左开右闭区间
    while (left < right) { //终止条件
      let mid = left + Math.floor((right - left + 1) / 2);
      if (arr[mid] < target) { // 目标值在右边
        left = mid; // 更新左边界
      } else if (arr[mid] > target) {  // 目标值在左边
        right = mid - 1; // 更新右边界
      } else {
        return mid;
      }
    }
  }

• 4、开区间写法

const search4 = (arr, target) => {
  let left = -1, right = arr.length; // 开区间
  while (left + 1 < right) { //终止条件
    let mid = left + Math.floor((right - left) / 2);
    if (arr[mid] < target) { // 目标值在右边
      left = mid; // 更新左边界
    } else if (arr[mid] > target) {  // 目标值在左边
      right = mid; // 更新右边界
    } else {
      return mid;
    }
  }
}```