2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't have a proof, but I don't think you can do better than $O((\lg |B|)^2)$. I suspect this might follow from a proof of optimality of binary search. Dividing $B$ up into intervals of (average) size $|B|/|A|$ doesn't help improve the asymptotics, since you still need to do binary search on those intervals, and each one of those binary searches takes $\Theta(\lg(|B|/|A|))$ time, which remains $\Theta(\lg |B|)$, since $\lg (n/\lg n) = \lg n - \lg \lg n = \Theta(\lg n)$. $\endgroup$ – D.W. Jun 10 '14 at 7:00
  • $\begingroup$ For $|A|$ growing as $|B| / \log |B|$, we can get it in $\mathcal O(|B|(\log\log|B|)/\log|B|)$ by dividing $B$ into $|A|$ intervals, finding which interval each element of $A$ lies in with the merge algorithm, and binary searching within each interval. That tells us there is room for improvement, but it doesn't say much about how much improvement is possible. Maybe a more sophisticated algorithm or a different choice of the relationship between $A$ and $B$ would give better results. $\endgroup$ – user2357112 supports Monica Jun 10 '14 at 7:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.