Suppose we have two sorted arrays $A$ and $B$, and we want to find the indices in $B$ of all elements of $A$. We can do this in $\mathcal O(|A|\log|B|)$ time by simply binary searching $|A|$ times. We can do it in $\mathcal O(|A| + |B|)$ time by iterating through the arrays together like the merge phase of a mergesort; this may or may not be an improvement, depending on the sizes of $A$ and $B$.
Can we do better? I don't expect any substantial improvement for $|A| \in \mathcal O(1)$ or $|A| \in \mathcal O(|B|)$, but for, say, $|A| \in \mathcal O(\log |B|)$, can we do better than $\mathcal O((\log |B|)^2)$? My ideas so far have been about some sort of adaptation of binary search that divides $B$ into a number of intervals depending on $|A|$, but I'm not yet sure whether it's an improvement.