# Maximum integer in a sorted list which also is in an unsorted list

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?

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
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.

• A tiny change that could save a lot of time: initialise Best to A - 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. Mar 11 at 19:22
• @gnasher729 The first is a good call, the second already happens on the last line.
– orlp
Mar 11 at 19:32