algorithm - 分而治之 - 找到包含唯一元素的两个大小相等的数组之间的中位数？

Question

我正试图解决这样一个问题: nth smallest number among two databases of size n each using divide and conquer

据我所知，“比较中位数/中位数的中位数”算法会给我们解决方案吗？ 我的问题是我是否理解正确。

array 1: [7 8 6 5 3]
array 2: [4 10 1 2 9] 

首先，找出每个的中位数。我们可以通过查询 k=n/2 来做到这一点，其中 n 是该数组的大小。作为本例中第三小的元素，第一个数组为 6(称为 m1)，第二个数组为 4(称为 m2)。

自 m1 > m2 ，使用该数组中小于 m1 和大于 m2 的元素创建 2 个数组。

array 1: [5 3]
array 2: [10 9]

^ 我们如何找到小于 m1 和大于 m2 的元素？ 我们是否只取 m1 和 m2 并将它们与各自数组中的每个元素进行比较？我知道这在两个数组都排序时有效，但首先对它们进行排序是否允许我们仍然获得 O(log(n)) 查询？

我假设我们可以继续使用我们的特殊查询(我们可以吗？)来获取该特定数组的 k=n/2 最小元素(中值)。如果是这种情况，我们查询 k=n/2=1，留下新的 m1 = 3。 , m2 = 9 .

m1 < m2 ，因此我们使用该数组中大于 m1 且小于 m2 的元素制作 2 个数组。

因为数组 2 中没有小于 m2 = 9 的元素，我们只剩下一个数组，其中一个元素大于 m1 = 3 .

[5] <- 这是中位数

我也有兴趣通过归纳查看正确性证明(即找到中位数)。

Answer 1

中值算法的O(n) meidan实际上是对数组进行分区，使得前面的元素小于它，后面的元素大于它。

当您以中位数的中位数作为基准进行递归时，您正在对数组进行分区，使其看起来像

(小于中位数的元素)-p-(大于中位数的元素)

关于正确性，当你第一次查询 k = n/2 时。你得到 m1 和 m2(m1 > m2)。现在你知道有超过 n 个元素小于 m1。所以它后面的元素永远不会成为中位数的候选者。
m2 之前的元素类似。他们前面有 n 个以上的元素，所以他们永远不会成为中位数的候选者。因此中位数必须位于第二个数组的后半部分和第一个数组的前半部分。

但是现在当你递归时你应该记住你计算了第二个数组的 n/2 个元素，所以你需要找到在两个数组的排序联合中占据第 n/2 个位置的元素(下半场和上半场)。

这似乎是渐近最优的，因为您总是将要递归的数组的大小减半。类似于 O(n) + O(n/2) + O(n/4) ... = O(n)。

对于排序数组，你可以做到这一点是 O(logn)。