List Intersection and Search

def intersect(list1, list2):
    if len(list1) > len(list2):
        list1, list2 = list2, list1
    result = []
    for x in list1:
        left, right = 0, len(list2)
        while left < right:
            mid = int((right - left)/2) + left
            if list2[mid] > x:
                right = mid
            elif list2[mid] < x:
                left = mid + 1
            else:
                result.append(x)
                break
    return result

• Swap so that list1 is the shorter list (length $k$).
• For each element in the shorter list, binary search in the longer list (length $n$): $O(\log n)$ each, $O(k \cdot \log n)$ in total.

1. Consider $\ln$ instead of $\log$; the difference is only a constant factor.
2. $e^x \geq 1 + x$ implies $\ln(1 + x) \leq x$ for all $x > -1$.
3. With $x = n/k$: $\ln(1 + n/k) \leq n/k$.
4. Therefore $k \cdot \ln(1 + n/k) \leq k \cdot n/k = n \leq k + n$.
5. Hence $O(k \cdot \log(1 + n/k)) \subseteq O(k + n)$. $\blacksquare$

If the lists differ in length by more than a factor of, say, 10 ($n/k > 10$), use galloping search; otherwise use the zipper. Galloping search is asymptotically always better or equal, but it is a more complex algorithm with a larger constant factor. Only if $k \ll n$ does the asymptotic advantage pay off; otherwise the simpler zipper is faster in practice (as observed in the exercises). (The official solution writes “$k/n$ less than 10”, meaning $n/k > 10$.)

The number of jumps is $k = \lceil \log_2(i+1) \rceil$.

1. After $k$ jumps the position checked is $0 + 1 + 2 + \ldots + 2^{k-1} = 2^k - 1$, and the search stops there, so $2^k - 1 \geq i \iff k \geq \log_2(i+1)$.
2. The position before that is $2^{k-1} - 1$, where it did not stop, so $2^{k-1} - 1 < i \iff k - 1 < \log_2(i+1)$.
3. Hence $k = \lceil \log_2(i+1) \rceil$.

Exponential phase: check positions $j_i = 2^i - 1$ until $A[j_k] \geq x$; then binary search in $[j_{k-1}, j_k]$.

1. Since $j_{k-1} < d$: $2^{k-1} - 1 < d$, hence $2^{k-1} \leq d$ and $k \leq \log_2 d + 1$. The exponential phase takes $O(k) = O(\log d)$ steps.
2. Hence $j_k \leq 2^{\log_2 d + 1} - 1 < 2d$. The binary search halves the interval in every step: $O(\log(2d)) = O(\log d)$ steps.
3. Together: $O(\log d)$. $\blacksquare$

def exponential_search(A, x):
    i = 0
    while A[i] < x:
        i = min(max(2 * i, 1), len(A) - 1)
    return i

Start at index 0 and double $i$ (max(2*i, 1) advances from 0 to 1), clamped to len(A) - 1. The loop runs $O(\log(1 + j))$ times because $i$ doubles in each iteration; it stops at the first probed $i \geq j$, and the previous probe $i/2 < j$ gives $i < 2j$.

def merge(A, B):
    i = j = 0
    res = []
    while i < len(A) or j < len(B):
        if j == len(B) or (i < len(A) and A[i] <= B[j]):
            res.append(A[i])
            i += 1
        else:
            res.append(B[j])
            j += 1
    return res

Two-pointer merge (zipper): at each step take the smaller of A[i] and B[j] (or whichever list has elements left). Every element is processed once: $O(|A| + |B|)$.