2
$\begingroup$

If I have a sorted list $A=[a_1, \dots, a_n]$ such that the integers $a_1\leq a_2\leq\dots\leq a_n$, and an unsorted list $B=[b_1, \dots, b_k]$, which includes at least one integer also in $A$, can I then find the maximum integer in $A$ which also is in $B$ in $O(k\log n)$ time? If so, how?

$\endgroup$
4
$\begingroup$

Are you familiar with binary search? If not, look that up. It has complexity $O(\log n)$ and will find you the index $i$ where you would insert $x$ into $A$ to maintain sorted order. From this you can instantly see whether $x$ already exists in $A$ by checking whether $A[i] = x$.

Then, do this for $b_1, b_2, \dots$, checking for each whether it is in $A$ in $O(\log n)$ time, and if yes, whether it is bigger than the current best found.

You do this $k$ times to find the biggest element that is in both $A$ and $B$ in $O(k \log n)$ time.


You can even be a bit smarter, like such:

lo = 1
best = A[1] - 1
for b in B:
    if b > best:
        i = binary_search(A, lo, n, b)
        if A[i] == b:
            best = b
            lo = i + 1

This doesn't change the worst case complexity but will avoid needless binary searches, and make the bounds on the binary searches that you do tighter.

$\endgroup$
2
  • $\begingroup$ A tiny change that could save a lot of time: initialise Best to A[1] - 1 instead of -Inf, just in case lots of elements in B are too small to be in A. And once Best gets bigger, you can restrict the binary search to the sub range containing the numbers >= Best. $\endgroup$ – gnasher729 Mar 11 at 19:22
  • $\begingroup$ @gnasher729 The first is a good call, the second already happens on the last line. $\endgroup$ – orlp Mar 11 at 19:32

Your Answer

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

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