first intersection of two arrays of integers - double binary search feasible?

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?

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

• 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

• Take that higher number and do a binary search for it in list B.

• If found done.

• 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.

• Do a binary search for that value is list A.

• If found done

• If not found take the number above the last search location in list A.

• Repeat steps 3–7 switching back and forth between lists.

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

StackExchange Computer Science Q#37073, answer score: 3