0
$\begingroup$

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 ?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Hint: can you find the size of such an array in O(log n) time? $\endgroup$
    – Jakube
    Nov 7, 2020 at 19:10
  • $\begingroup$ @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...? $\endgroup$
    – Swarnabja Bhaumik
    Nov 7, 2020 at 19:15
  • $\begingroup$ 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. $\endgroup$
    – Jakube
    Nov 7, 2020 at 19:23

1 Answer 1

Reset to default
1
$\begingroup$

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.
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This is not a coding site, so I removed the code. $\endgroup$
    – Yuval Filmus
    Apr 18, 2021 at 5:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.