在2分排序列

Question

找到共同的元素

可能重复：
The intersection of two sorted arrays

我们有两个排序数组a和b，除了比较一个与其他阵列，所有的元素如何设计一个最佳算法来查找具有共同元素的数组？

Answer 1

保持两个指针：每个数组一个。

i <- 0, j <- 0 
repeat while i < length(arr1) and j < length(arr2): 
    if arr1[i] > arr2[j]: increase j 
    else if arr1[i] < arr2[j]: increase i 
    else : output arr[i], increase both pointers 

的想法是，如果数据进行排序，如果元素是一个数组“过大”，这将是“太大”左阵列中的所有其他元素 - 因为它是排序。

该解决方案需要对数据进行一次遍历。 O(n)（具有良好的常数）。

Answer 2

除了比较一个与其他阵列中的所有元素

您将有比较A []到B []为了知道他们是相同的 - 除非你知道很多他们可以容纳什么样的数据。比较的性质可能有很多解决方案，可根据需要进行优化。

如果数组非常严格创建，即只有已知模式的顺序值，并且始终从已知点开始，则可以只查看每个数组的长度并知道是否所有项都是常见的。

这遗憾的是不听起来像一个非常现实的或有用的阵列等你回检查A [i]于B []

Answer 3

如果两个阵列（比如，A具有N元件的长度和B有M元素）是相似的，那么最好的方法是执行线性搜索另一个数组中的一个数组元素。当然，由于数组已经排序，所以下一次搜索应该从前一次搜索停止的地方开始。这是“排序阵列合并”算法中使用的经典原理。 O(N + M)上的复杂性。

如果长度显著不同（比如，M << N），则更加最佳的方法是通过较短的阵列的元素以迭代，并使用二进制搜索寻找更长的阵列中的这些值。在这种情况下的复杂性是O(M * log N)。

正如你可以看到O(M * log N)优于O(N + M)如果M比N小得多，否则更糟糕。

应该触发从一种方法切换到另一种方法的阵列尺寸的差异取决于一些实际考虑因素。如果应该根据您的数据进行实际的实验来选择。

这两种方法（线性搜索和二元搜索）可以“混合”为单一算法。我们假设M <= N。在这种情况下，我们选择步骤值S = [N/M]。您从数组A中获取第一个元素并执行跨步线性搜索数组B中的该元素，并执行步骤S，这意味着您要检查元素B[0], B[S], B[2*S], B[3*S], ...等。一旦找到潜在包含正在搜索的元素的索引范围[S*i, S*(i+1)]，则切换到二进制在数组B的该段内搜索。完成。下一个元素A的横坐标线性搜索从上次搜索停止的位置开始。 （作为附注，选择等于2的幂的S的值可能是有意义的）。

这种“混合”算法是存在的两个排序阵列最渐近最优的搜索/合并算法。然而，在实践中，根据阵列的相对大小选择二进制或线性搜索的更简单方法非常好。