Question

两个有序数组中位数

Answer 1

输入： 两个有序数列
输出： 总体数列的中位数
要求 时间复杂度 O(log(m+n))
用例： [1,3] [2] ====> The median is 2.0
[1,2] [3,4] ====> The median is 2.5

这个题目要求了时间复杂度。如果不要求时间复杂度，可以直接放到一个整体的数列中，然后用一个排序算法，之后就是一个有序数列的中位数。
但是，要求时间复杂度是 log 形式的，所以一定是分治法。

依旧按照之前的将两个有序数列合为一个有序数列的方法。考虑时间复杂度。
a[n] ①②③...
b[m] ①②③...
c[m+n]
比较 第一个数列的第一个数字和第二个数列的第一个数字，将小的放进新的数列的第一个，知道某一个数列全部没有，之后将另外一个数列剩下的放在后面。即得到了第三个有序数列。