# 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

We need to first find the length of array in long time as it is not given.

1. Start with length as 1 and increase it as multiple of 2.
2. Check whether element at length-1 position is positive or not.
3. If so repeat steps 1 and 2.
4. If not return the index position it will be the maximum size of the array. As it is mentioned beyond the maximum position element value is negative.
5. Once the length of array is known simple binary search alto will be applied to search element and it will be searched in both the array and intersection point will be determined.
• This is not a coding site, so I removed the code. Apr 18, 2021 at 5:55