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.