ISI2020-PCB-CS: 3

Question

You are given two sorted arrays $X[\;]$ and $Y[\;]$ of positive integers. The array sizes are not given. Accessing any index beyond the last element of the arrays 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 exist $i, j$ such that $X[i]=Y[j]=p.$

Given a positive integer $q$, design an algorithm (in pseudocode ) to check if $q$ is an intersection point between $X$ and $Y$. No marks will be awarded if the time complexity of your algorithm is linear (or higher) in the maximum size of $X$ and $Y.$

Comments

Basic binary search to find Q on both the array will work i guess. Complexity will be O(Max(Log(|X|), Log(|Y|)).

Answer 1

In question it is given that both arrays are sorted and time complexity of our solution should be strictly lesser than linear.

These two things are enough to tell that we need to apply some form of binary search type algorithm.

Formally the problem statement is to find location of $q$ in both arrays.

But we have one problem we do not have the array sizes, rather the array contains $-1$ beyond the last element of array.

So, what we can do here is we start traversing the array from $i=1$ and everytime $arr[i]<q$ we set $i=2*i$. We do this until we get $arr[i]=-1$ or $arr[i]>q$.

Now, from above few steps we got $2$ array indices between which it is guaranteed that $q$ will occur, if it exists viz $i$ and $\frac{i}{2}$.

Now, we can use our standard binary search algorithm between $left = \frac{i}{2}$ and $right = i$. The only extra modification needed is that we have to make sure when $arr[mid] = -1$ we update the $right$ as $right = mid -1$.

The below function $findLoc$ takes an array and $q$ as an input and returns the location of $q$ in that array if it exists, otherwise it returns $-1$.

int findLoc (int *arr, int q) { 
   int i = 0, right, left;
   
   if (arr[i] == q) return i;
   
   for (i = 1; arr[i]!=-1; i = i*2) {
      if (arr[i] == q) return i;
      if (arr[i] > q) {
         break;
      }
   }
   
   right = i;
   left = i/2;
   while (right>=left) {
      int mid = (right + left) /2;
      if (arr[mid] == q) return mid;
      else if (arr[mid] > q || arr[mid] = -1) right = mid - 1;
      else left = mid + 1;
   }

   if (left > right) return -1;
}

Both the loops in the above code have logarithmic time complexity, $findLoc$ function also has logarithmic time complexity.