04-寻找两个有序数组的中位数-findMedianSortedArrays

[TOC]

一、题目

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

二、解题思路

• log + 有序数组 -> 二分法
• 第 k 大的数前面一定有 k - 1 个数。
  • 
• 题目转换为，若总个数为奇数，则找第(n+m+1)/2小的数；若为偶数，则找第(n+m)/2和(n+m)/2+1小的数后，取平均值。

三、算法实现

参考教程：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/he-bing-yi-hou-zhao-gui-bing-guo-cheng-zhong-zhao-/

有时间要补图解

var findMedianSortedArrays = function (nums1, nums2) {
  let len1 = nums1.length,
    len2 = nums2.length;
  // 为了让搜索范围更小
  if (len1 > len2) {
    return findMedianSortedArrays(nums2, nums1)
  }

  let low = 0,  // 符合条件的下边界
    high = len1;  // 符合条件的下边界
  let totalLeft = (len1 + len2 + 1) >>> 1;

  while (low < high) {
    let mid1 = (low + high) >>> 1,
      mid2 = totalLeft - mid1;
    if (nums2[mid2-1] > nums1[mid1]) {
      low = mid1 + 1
    } else {
      // 不取mid1-1,是为了避免越界
      high = mid1
    }
  }

  let max1 = low === 0 ? -Infinity : nums1[low-1]
  let min1 = low === len1 ? Infinity : nums1[low]

  let low2 = totalLeft - low
  let max2 = low2 === 0 ? -Infinity : nums2[low2-1]
  let min2 = low2 === len2 ? Infinity : nums2[low2]

  if (((len1 + len2) & 1) == 1) {
    return Math.max(max1, max2);
  } else {
    return ((Math.max(max1, max2) + Math.min(min1, min2))) / 2;
  }
};