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?
first intersection of two arrays of integers - double binary search feasible?
algorithms;binary search
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.