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.