[Solved]: first intersection of two arrays of integers – double binary search feasible?

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.