题目:

给定两个大小为 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
示例 3：

输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
示例 4：

输入：nums1 = [], nums2 = [1]
输出：1.00000
示例 5：

输入：nums1 = [2], nums2 = []
输出：2.00000

我的实现: （双指针）

var findMedianSortedArrays = function (nums1, nums2) {
  const num1_len = nums1.length;
  const num2_len = nums2.length;
  const sum_len = num1_len + num2_len;
  let num1_index = 0;
  let num2_index = 0;
  let result = 0;
  if (sum_len % 2 == 0) {
    for (let i = 0; i < sum_len / 2; i++) {
      if (num1_index < num1_len && num2_index < num2_len) {
        if (nums1[num1_index] < nums2[num2_index]) {
          result = nums1[num1_index++];
        } else {
          result = nums2[num2_index++];
        }
      } else {
        if (num1_index === num1_len) {
          result = nums2[num2_index++];
          continue;
        }
        if (num2_index === num2_len) {
          result = nums1[num1_index++];
          continue;
        }
      }
    }
    if (num1_index < num1_len && num2_index < num2_len) {
      if (nums1[num1_index] < nums2[num2_index]) {
        result = (result + nums1[num1_index]) / 2;
      } else {
        result = (result + nums2[num2_index]) / 2;
      }
    } else {
      if (num1_index === num1_len) {
        result = (result + nums2[num2_index]) / 2;
      }
      if (num2_index === num2_len) {
        result = (result + nums1[num1_index]) / 2;
      }
    }
  } else {
    for (let i = 0; i < sum_len / 2; i++) {
      if (num1_index < num1_len && num2_index < num2_len) {
        if (nums1[num1_index] < nums2[num2_index]) {
          result = nums1[num1_index++];
        } else {
          result = nums2[num2_index++];
        }
      } else {
        if (num1_index === num1_len) {
          result = nums2[num2_index++];
          continue;
        }
        if (num2_index === num2_len) {
          result = nums1[num1_index++];
          continue;
        }
      }
    }
  }
  return result;
};

image.png

涉及问题:
第K小数

image.png

二分查找
https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/
满足:

image.png

不满足状况:

image.png

const findMedianSortedArrays = (nums1, nums2) => {

  // //使nums1 长度小于 nums2,方便后面使用
  if (nums1.length > nums2.length) [nums1, nums2] = [nums2, nums1];

  const m = nums1.length;
  const n = nums2.length;

  //左边元素个数
  const totalLeft = (m + n + 1) / 2 >> 0;

  //在nums1 [0,m] 中寻找 分割线 
  //使得nums1[i-1] <= nums2[j] && nums[j-1] <= nums1[i]
  let left = 0;
  let right = m;

  while (left < right) {
    const i = left + ((right - left + 1) / 2 >> 0);
    const j = totalLeft - i;
    if (nums1[i - 1] > nums2[j]) {
      //下一轮 搜索的区间 [left,i-1]
      right = i - 1;
    } else {
      //下一轮 搜索的区间 [i,right]
      //[left(i),right]
      left = i;
    }
  }
  const i = left;
  const j = totalLeft - i;

  const num1LeftMax = i == 0 ? -Infinity : nums1[i - 1];
  const num1RightMin = i == m ? Infinity : nums1[i];
  const num2LeftMax = j == 0 ? -Infinity : nums2[j - 1];
  const num2RightMin = j == n ? Infinity : nums2[j];

  if ((m + n) % 2 == 1) {
    //奇数
    return Math.max(num1LeftMax, num2LeftMax);
  } else {
    //偶数
    return (Math.max(num1LeftMax, num2LeftMax) + Math.min(num1RightMin, num2RightMin)) / 2;
  }
}

const a = [1, 2];
const b = [3, 4, 5, 8]
console.log(findMedianSortedArrays(a, b));