寻找两个正序数组的中位数

题解思路

方法：二分查找（$O(\log (m+n))$）

我们不需要真的合并 nums1 和 nums2，而是通过 二分查找 在 较短的数组上 进行分割，确定中位数。

1. 目标

我们要找到 合并后数组的中位数：

• 若总长度是奇数，中位数是第 (m+n)//2 + 1 个元素。

Leetcode 68.寻找两个正序数组的中位数-原题链接

题目内容

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

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

输入描述

• 第一行输入一个整数 m，表示数组 nums1 的长度。
• 第二行输入 m 个整数，表示数组 nums1。
• 第三行输入一个整数 n，表示数组 nums2 的长度。
• 第四行输入 n 个整数，表示数组 nums2。

输出描述

输出一个浮点数，表示两个数组的 中位数，精确到 5 位小数。

样例1

输入

2
1 3
1
2

输出

2.00000

说明

合并数组 = $[1,2,3]$ ，中位数 $2$

样例2

输入

2
1 2
2
3 4

输出

2.50000

说明

合并数组= $[1,2,3,4]$ ，中位数 $(2 + 3) / 2 = 2.5$

提示：

• $nums1.length == m$
• $nums2.length == n$
• $0 <= m <= 1000$
• $0 <= n <= 1000$
• $1 <= m + n <= 2000$
• $-10^6 <= nums1[i], nums2[i] <= 10^6$