该算法还不错——在我看来，它比 SO 上通常引用的算法要好，因为它要简单得多——但它有一个巨大的缺陷：它要求两个向量都至少有k元素。（问题是它们都有相同数量的元素，n但从未指定过n ≥ k；该函数甚至不允许您告诉它向量有多大。但是，这很容易解决。我将其留作练习现在。一般来说，我们需要一个像这样的算法来处理不同大小的数组，它确实如此；我们只需要清楚先决条件。）
floorand的使用ceil很好而且很具体，但可能会令人困惑。让我们以最一般的方式来看这个。此外，引用的解决方案似乎假设数组是 1 索引的（即A[1]是第一个元素，而不是A[0]）。然而，我将要写的描述使用更像 C 的伪代码，所以它假定这A[0]是第一个元素。因此，我将编写它来查找k组合集中的元素，即元素。最后，我要描述的解决方案与提出的解决方案略有不同，这在最终条件下会很明显。恕我直言，它稍微好一点。(k+1)th
好的，如果x是序列中的元素，则序列k中恰好有k小于 的元素x。（我们不会处理有重复元素的情况，但差别不大。见注3。）
假设我们知道A并且B每个都有一个元素k。（请记住，这意味着它们每个都至少有k + 1元素。）选择任何小于k;的非负整数。我们会调用它i。让我们j成为k - i - 1（这样i + j == k - 1）。[参见下面的注释 1。] 现在，看看元素A[i]和B[j]. 假设A[i]更小，因为我们只需要在另一种情况下更改所有名称。请记住，我们假设所有元素都是不同的。所以这就是我们目前所知道的：
1 )有i元素A< A[i]
2 )有j元素B< B[j]
3)A[i] < B[j]
4）从（2）和（3），我们知道：
5 )至多j有B< A[i]
6) 由 (1) 和 (5) 可知：
7）至多有i + j元素在里面A并且B一起是< A[i]
8) 但是i + j是k - 1，所以实际上我们知道：
9)k合并数组的元素必须大于A[i]（因为A[i]最多为 element i + j）。
因为我们知道答案必须大于A[i]，所以我们可以丢弃 A[0] 到 A[i] （实际上，我们只是增加一个数组指针，但实际上我们会丢弃它们）。但是，我们现在已经i + 1从原始问题中丢弃了元素。所以在新的元素集（在缩短A的和原始的B）中，我们需要 element k - (i + 1)，而不是 element k。
现在，让我们检查前提条件。我们说两者A都有B一个元素k元素，所以它们都至少有k + 1元素。在新问题中，我们想知道缩短A的和原始的是否B都至少有k - i元素。很明显B，因为k - i没有更大的k。此外，我们i + 1从A. 最初它至少有k + 1元素，所以现在它至少有k - i元素。所以我们在那里没问题。
最后，让我们检查终止条件。一开始我说过我们选择非负整数i等等j。i + j == k - 1如果 ，那是不可能的k == 0，但可以做到k == 1。所以我们只需要在k达到 0 时做一些特殊的事情，在这种情况下我们需要做的是 return min(A[0], B[0])。[这是一个比您查看的算法更简单的终止条件，请参见注 2。]
那么有什么好的挑选策略i呢？我们最终会从问题中删除一个i + 1或多个k - i元素，我们希望它尽可能接近一半的元素。所以我们应该选择i = floor((k - 1) / 2)。尽管它可能不会立即显而易见，但这会使j = floor(k / 2).
我忽略了我解决问题的地方A并且B元素更少的地方。这并不复杂；我鼓励你自己考虑一下。
[1] 您正在查看的算法选择i + j == k（如果k是偶数），并删除其中一个i或j元素。我的选择i + j == k - 1（总是）可能会使其中一个更小，但随后它会下降i + 1或j + 1元素。所以它应该收敛得更快一些。
i + j == k[2] 选择（他们的）和（我的）之间的区别在i + j == k - 1最终条件下很明显。在他们的表述中，两者i和都j必须是正数，因为如果其中一个为 0，则存在丢弃 0 个元素的风险，这将是一个无限递归循环。所以在他们的表述中， 的最小值可能k是 2，而不是 1，因此他们的终止情况必须处理k == 1，这涉及到四个元素之间的比较，而不是两个。对于它的价值，我相信“从两个排序向量中找到第二小的元素”的最佳解决方案是： min(max(A[0], B[0]), min(A[1], B[1 ]))，这需要三个比较。这不会使他们的算法变慢；只是更复杂。
[3] 假设元素可以重复。其实这并没有改变什么。该算法仍然有效。为什么？好吧，我们可以假设 in 中的每个元素A实际上是一对具有实际值和实际索引的对，对于 in 中的每个元素也是B如此，并且在比较向量中的值时，我们使用索引作为决胜局。在向量之间，我们优先考虑Aif中的所有元素A[i] ≤ B[j]；否则对B. 这实际上并没有改变实际的代码，因为我们实际上不需要做任何不同的比较，但它使证明中的所有不等式都有效。