Algorithm to find the intersection of sorted sets

1
votes

I have been looking over ways to find the intersection of two sorted sets that are more efficient than doing so iteratively. Eventually my searching brought me to this question: intersection and union of n-arrays in C . However, I do not understand how the intersection of two sets is equal to the intersection of the intersection of two subsets. I want to try to figure out how to do the divide and conquer algorithm with recursion, but I can't understand how the example given would work.

More specifically, how would a divide and conquer algorithm ever work for two sets such as:

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

It doesn't seem like a divide and conquer algorithm would exist that would actually consistently find the intersection at 3.

2
algorithmdivide-and-conquerset-intersection
How about a HashSet? – 6324
That link is about multiple sets intersection or union. For two sets I can't think of anything faster then iterating through the two sorted arrays, like here, which is O(N). – Bob__

2 Answers

2
votes

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

That's not what your link is talking about (because it's wrong, as you recognized).

Finding the the intersection of a sorted set, ie. the common elements of two sorted arrays,
is not possible without at least iterating them. It won't get better than O(N).

-1
votes

Between two arrays find one which last element is greater than the first element of other.

For example:

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

Select array A. Apply Binary search on A from right to left to find an element such that:

A[i] >= B[0]

Now use linear search from this two arrays:

A[i......n]
B[0......m]

Where n and m are the length of A and B respectively.

I think it has less complexity than linear search at first attempt.