Fast Term Intersections & Sorted Array Merging
Multi-word queries (`apple AND banana`) intersect two posting lists. Because document IDs inside posting lists are sorted monotonically, a two-pointer merge finds matches in linear $O(L_1 + L_2)$ time without costly hash lookups ⚡🎯.
def intersect_postings(p1, p2):
i, j = 0, 0
matches = []
while i < len(p1) and j < len(p2):
if p1[i] == p2[j]:
matches.append(p1[i])
i += 1
j += 1
elif p1[i] < p2[j]:
i += 1
else:
j += 1
return matches
# Document IDs containing each word:
docs_python = [1, 5, 8, 12, 19, 25]
docs_async = [2, 5, 12, 20, 25, 30]
shared_docs = intersect_postings(docs_python, docs_async)
print(f"Docs containing both terms: {shared_docs} 🚀")
# 53. Fast Term Intersections & Sorted Array Merging If you convert posting lists to raw Python `set(p1) & set(p2)`, Python must allocate hash tables, compute hash buckets for millions of document IDs, and thrash CPU caches. Search engines never use hash sets for posting intersections 🛑. ```python # The Two-Pointer Convergence: # P1: [ 3, 7, 12, 19, 24 ] (ptr i) # P2: [ 7, 10, 12, 28, 30 ] (ptr j) # 1. P1[0] < P2[0] (3 < 7) -> i++ # 2. P1[1] == P2[0] (7 == 7) -> MATCH 7! i++, j++ # 3. P1[2] > P2[1] (12 > 10) -> j++ # 4. P1[2] == P2[2] (12 == 12)-> MATCH 12! i++, j++ ``` ### High-Performance Search Optimization 1. **Sorted Guarantee**: Because document IDs are generated sequentially upon ingest, every posting list is naturally sorted in ascending order. 2. **Linear Merge**: Iterating with two pointers processes both lists in a single linear pass of $O(L_1 + L_2)$ steps. 3. **Skip Pointers**: In production posting lists, jump pointers are placed every $\sqrt{L}$ elements. If `p1[i] = 100` and `p2[j] = 5000`, the algorithm can skip forward hundreds of entries in $O(1)$ instead of incrementing $i$ one by one ⚡. --- ### Interactive Pop-Quiz 🧠 #### What is the time complexity of intersecting two sorted posting lists of lengths $L_1$ and $L_2$ using the two-pointer technique? - [ ] $O(L_1 + L_2)$ linear time ⚡ - [ ] $O(L_1 \times L_2)$ quadratic time - [ ] $O(1)$ constant time - [ ] $O((L_1 + L_2)^2)$ exponential time --- ### Practical Challenge 🎯 Implement `intersect_postings(p1, p2)` using the two-pointer sorted algorithm. Intersect `p1 = [10, 20, 30, 40, 50]` and `p2 = [15, 20, 35, 40, 60]`. Assert the intersected document list is `[20, 40]`, and print the result. <details> <summary>Solution</summary> ```python def intersect_postings(p1, p2): i, j = 0, 0 matches = [] while i < len(p1) and j < len(p2): if p1[i] == p2[j]: matches.append(p1[i]) i += 1 j += 1 elif p1[i] < p2[j]: i += 1 else: j += 1 return matches p1 = [10, 20, 30, 40, 50] p2 = [15, 20, 35, 40, 60] res = intersect_postings(p1, p2) assert res == [20, 40] print(res) ``` </details>