Given two lists **[T]**, the following algorithm finds
the intersection (values common to both lists) in **O(min(m, n))**
time and **O(min(m,n))** space provided that:

- The two lists are sorted.
**T**is orderable and comparable.- Both lists do not contain repeat elements.

def intersection(A, B): a = len(A) s = 0 R = [] for n in B: for i in range(s, a): c = A[i] if n < c: break s += 1 if n == c: R.append(n) break if s == a: break return R

Another algorithm for when intersections should be found
in place. This modifies **A**. Most of the ugliness
from the code stems from the fact that it is hard to
iterate backwards in Python. Again all conditions from
the first algorithm need to be satisfied. However:

- Space complexity is essentially
**O(1)** - Time complexity is higher, at worse
**O(max(n,m))**due to the additional deletes.

def intersection(A, B): b = len(B) - 1 a = len(A) - 1 # Find intersections, and set a to be the index # where the algorithm should search from for i in range(b, -1, -1): n = B[i] for j in range(a, -1, -1): c = A[j] if n > c: break a -= 1 if n == c: break del A[j] # everything below a is not included in the other # set, so delete for j in range(a, -1, -1): del A[j] return A

Both algorithms exploit the fact that the lists are
already sorted, and break from the inner loop early
to avoid a full scan whenever it makes sense to avoid
**O(mn)**. It is possible to use a binary search
instead of the linear scan to determine the index.

However, that would give a worse time complexity should
the lists have very tighly clustered values: linear
search is at worse, **O(n)** but **Ω(1)**. However
a binary search is almost always **O(log n)**. Case
in point:

Easy to find1in[1,2,3,4,5,6,7,8]using linear search. However a binary search needs ~3 steps.