I\'m interested to find the fastest possible way to find the first element of an

Question

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?

Explanation / Answer

The O(logn+logm) algorithm is impossible. Any algorithm that purports to find an intersection between the sets must be ?(n), since if it is faster than ?(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,

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.