4
$\begingroup$

I'm interested to find the fastest possible way to find the first element of an intersection of two integers arrays (first match)

Looking for the 'fastest' algorithm I have seen different methods with different time complexities (to calculate the arrays intersection)

i.e: $O(N+M)$, $O(N * log(M)$,...

Also I have seen some references to an algorithm able to do this by implementing a double binary search to find the first match with time complexity $O(log(n)+log(m))$

Do you know about some reliable source or pseudo-code about this algorithm if such exists?

Improve this question
$\endgroup$
2
  • $\begingroup$ Are the arrays sorted? This is usually a requirement to use binary search. $\endgroup$
    – Tom van der Zanden
    Commented Jan 8, 2015 at 20:25
  • $\begingroup$ Yes, they are sorted. $\endgroup$
    – Jesus Salas
    Commented Jan 8, 2015 at 22:47

2 Answers 2

Reset to default
2
$\begingroup$

The $O(\log n + \log m)$ algorithm is impossible. Any algorithm that purports to find an intersection between the sets must be $\Omega(n)$, since if it is faster than $\Omega(n)$ it could not examine all elements from the array but it must do so in order to be correct.

Consider the input where one set is the even numbers $\{2,4,6,\ldots,2n\}$ and the other set the odd nubmers $\{1,3,5,\ldots,2n-1\}$. If on this input the algorithm doesn't examine all of the elements from the first array, then assume it does not examine the element $2k$ from the first array. Then if presented with the same input but with $2k$ replaced by $2k-1$ it will incorrectly report there is no intersection. So any correct algorithm must examine all elements from at least one of the arrays.

The $O(n \log m)$ algorithm is trivial, it involves doing a binary search on one of the sets for each of the elements of the other set. This requires one of the arrays to be sorted. The sorting can almost be done in $O(n \log m)$, but there is a slight problem when $m$ is much bigger than $n$ (but I doubt you are interested in such technicalities).

$O(n+m)$ is possible, but this requires (to my knowledge) the arrays to be sorted. This can be achieved by walking through both sorted arrays simultaneously, repeatedly advancing the pointer into the array whose current element is lowest until you reach the end of either array or find an intersection.

Improve this answer
$\endgroup$
5
  • $\begingroup$ "but there is a slight problem when m is much bigger than $n$"... I'm curious about what is this problem. Could you expand your answer? Thanks! $\endgroup$
    – Jesus Salas
    Commented Jan 8, 2015 at 22:48
  • 1
    $\begingroup$ If $m >> n$, then we can not sort the array of $m$ numbers in $O(n \log m)$ time, so we would not be able to achieve the $O(n \log m)$ running time but rather $O(m \log m)$. We could still achieve $O(m \log n)$ by sorting the array of $n$ numbers and doing binary search on that. So to be fully accurate, the running time is $O(\max(m,n) \log{(\min(m,n)))}$. $\endgroup$
    – Tom van der Zanden
    Commented Jan 9, 2015 at 0:18
  • $\begingroup$ Tom, what is your opinion on GC_ answer? $\endgroup$
    – Jesus Salas
    Commented Jan 12, 2015 at 3:16
  • 1
    $\begingroup$ @JesusSalas His algorithm is not $O(\log n + \log m)$; I proved that that is impossible. He ends up doing a linear number of binary searches in the worst case so the algorithm is not any better than the $O(n \log m)$ one which loops over the elements of one array and does binary search on the other. Executing the "double binary search" on my example of even and odd numbers, it will start doing a binary search for $2$ in the list of odd numbers. It will then search for $3$ in the even list, search for $4$ in the odd list, and so on. $\endgroup$
    – Tom van der Zanden
    Commented Jan 12, 2015 at 20:07
  • $\begingroup$ The example given doesn't prove that all data needs to be visited. If the two sets are ordered, we can rely on that order to dispense with some comparisons, in the same way that search can be done in less than linear time. $\endgroup$
    – boisvert
    Commented Apr 14, 2020 at 9:50
3
$\begingroup$

There is a double binary search algorithm. It will only work is both lists are sorted. It is basically as follows.

  1. Check the first, lowest number on each list. Compare the numbers to find which number is higher. Assume that higher number is in List A
  2. Take that higher number and do a binary search for it in list B.
  3. If found done.
  4. If not found take the number above the last search location in list B For example, assume list A had a 5, and in list B you do a binary search and find 6 and 4 with no five in between. Take the 6 from list B.
  5. Do a binary search for that value is list A.
  6. If found done
  7. If not found take the number above the last search location in list A.
  8. Repeat steps 3–7 switching back and forth between lists.

That is the basic idea, if you want further information, let me know.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, I'll give it a shot and see how it works, I'll publish the code once done for other looking for this. $\endgroup$
    – Jesus Salas
    Commented Jan 12, 2015 at 3:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.