1.1. The input is $(A, B)$, where $A$ is an array of $m$ distinct, positive integers, $B$ is an array of $n$ distinct, positive integers, and $m \leq n$. Our goal is to return a list $C$ (in any order) of the intersection of $A$ and $B$. Describe an $O(n\log m)$-time algorithm for this problem and analyze its running time.
Sort $A$. Then, for each element $b$ in $B$, binary search for $b$ in $A$. If $b$ is in $A$, append $b$ to a list $C$ (initially empty).
ALG(A, B):
sort A
C = [empty list]
for b in B:
if b in A: # use binary search
add b to C
return C
Sorting $A$ takes $O(m\log m)$ time. The algorithm then makes $n$ iterations, and each iteration takes $O(\log m)$ time. Thus, the total running time is $O(m\log m) + n \cdot O(\log m) = O(n\log m)$.