我正试图解决一个完全像这样的问题：两个大小为n的数据库中的第n个最小数，每个数据库都使用分治法
据我所知，“比较中位数/中位数的中位数”算法可以为我们提供解决方案吗？我的问题是我是否正确理解了这一点。
array 1: [7 8 6 5 3]
array 2: [4 10 1 2 9]
首先，找到每个的中位数。我们可以通过查询k = n / 2来实现，其中n是该数组的大小。作为这种情况下的第3个最小元素，这给我们第一个数组6（称为this m1），第二个数组4（称为this 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] <-这是中位数
我也有兴趣通过归纳法查看正确性证明（即找到中位数）。
中值算法的O（n）meidan实际上是对数组进行分区，以使其之前的元素小于它，之后的元素大于它。
当以中位数的中位数作为枢轴进行递归时，您正在对数组进行分区，以使其看起来像
（小于中位数的元素）-p-（大于中位数的元素）
关于正确性，当您第一次查询k = n / 2时。您得到m1和m2（m1> m2）。现在您知道小于m1的元素多于n个。因此紧随其后的元素将永远不会成为中位数的候选者。
m2之前的类似元素。它们前面有n个以上的元素，因此它们永远不会成为中位数的候选者。因此，中位数必须位于第二个数组的后半部分和第一个数组的前半部分中。
但是现在递归时，请记住，第二个数组的n / 2个元素被计算在内，因此您需要找到在两个数组的并集中占据第n / 2个位置的元素（后半部分和上半年）。
这似乎是渐近最佳的，因为您总是将要递归的数组的大小减小到一半。类似于O（n）+ O（n / 2）+ O（n / 4）... = O（n）。
对于排序的数组，您可以这样做是O（logn）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句