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

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

思路

  1. 将问题转化为寻找第 K 小的数，可以标准化数组总数奇偶两种不同的情况
  2. searchK 方法可进行递归折半缩小查找范围
  3. 若两数组其一元素数量为 0，直接返回有元素素组的相应下标即可
  4. 若 k === 1，返回两数组首元素较小值即可
  5. 每次递归时，steps = Math.floor(k / 2)
  6. 因为初始参数的缘故，递归时需要待遍历的两数组长度不会同时小于 steps
  7. 若 nums1 待搜索长度小于 steps，可以将 start2 前移 steps，进而继续搜索第 k - steps 小的数
  8. 若两数组待搜索长度均不小于 steps，可以对比 nums1[start1 + steps - 1] 和 nums2[start2 + steps - 1] 大小并将较小值所在数组的搜索下标增加 steps
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var findMedianSortedArrays = function (nums1, nums2) {
  const searchK = (start1, start2, k) => {
    if (start1 >= nums1.length) {
      return nums2[start2 + k - 1]
    }
    if (start2 >= nums2.length) {
      return nums1[start1 + k - 1]
    }
    if (k === 1) {
      return Math.min(nums1[start1], nums2[start2])
    }
    const steps = Math.floor(k / 2)
    const val1 = start1 + steps - 1 < nums1.length ? nums1[start1 + steps - 1] : Number.MAX_SAFE_INTEGER
    const val2 = start2 + steps - 1 < nums2.length ? nums2[start2 + steps - 1] : Number.MAX_SAFE_INTEGER
    if (val1 < val2) {
      return searchK(start1 + steps, start2, k - steps)
    }
    return searchK(start1, start2 + steps, k - steps)
  }
  const length = nums1.length + nums2.length
  if (length % 2 === 1) {
    return searchK(0, 0, (length + 1) / 2)
  }
  return (searchK(0, 0, length / 2) + searchK(0, 0, length / 2 + 1)) / 2
}