查找排序集交集的算法

Question

我一直在寻找比迭代更有效的方法来找到两个排序集的交集。最终我的搜索让我想到了这个问题:intersection and union of n-arrays in C .但是，我不明白两个集合的交集如何等于两个子集的交集。我想弄清楚如何使用递归执行分而治之算法，但我无法理解给出的示例如何工作。

更具体地说，分而治之算法如何适用于两个集合，例如:

A = 1, 2, 3, 4
B = 3, 5, 6, 7

似乎不存在实际上始终如一地在 3 处找到交点的分而治之算法。

Answer 1

However, I do not understand how the intersection of two sets is equal to the intersection of the intersection of two subsets.

这不是您的链接所谈论的内容(因为它是错误的，正如您所认识到的)。

寻找有序集合的交集，即。两个排序数组的公共(public)元素，
至少不迭代它们是不可能的。它不会比 O(N) 更好。