# Find the intersection point between two sorted arrays with unknown lengths in lesser than O(n)

Two sorted arrays of positive integers, X[] and Y[] are given.But, the array sizes are unknown to us. We may assume that accessing any index beyond the last element of the array returns -1. The elements in each array are distinct but the two arrays may have common elements. An intersection point between the two arrays is an element common to both the arrays, i.e., p ( p>0 ) be an intersection point if there exists i,j such that X[i]=Y[j]=p

Given a positive integer q, how can we design an algorithm ( in pseudocode ) to check if q is an intersection point between X and Y in strictly less than O(n) time complexity.

I proceeded by thinking of applying binary search on both the arrays X and Y, since they are sorted and trying to find if q exists in both of them. But not knowing the lengths leads me astray.

• Hint: can you find the size of such an array in O(log n) time? Nov 7, 2020 at 19:10
• @Jakube...yeah was wondering about that, could it be such like I try accessing indexes in powers of 2, until I get a -1 flag...? Nov 7, 2020 at 19:15
• Sounds good. With that you can get an upper bound for the size in O(log n). You can then continue to find the exact size by doing a normal binary search, and do the normal binary search to find p. But you can also just do binary search straight when you have the upper bound. Nov 7, 2020 at 19:23