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.
Could anyone please help me with this ?