The question this module answers: how do I search pairs without checking every pair? A nested loop looks at all n² pairs. When the data has order (sorted values, or a direction you can scan in), two indices that only ever move forward can rule out a whole row or column of pairs with one comparison, and finish in O(n).
ML context. Order is everywhere in ML pipelines:
- Merging sorted prediction lists, sorted event logs or sorted shards.
- De-duplicating sorted ids before a join.
- Sweeping sorted scores to compute ROC AUC or pick a threshold.
- Matching two sorted streams (users seen in both, timestamps within a gap).
1. The problem: pair search is O(n²)
Task: in a sorted array, is there a pair that sums to target?
n(n − 1)/2 pairs. At n = 10⁵ that's 5 × 10⁹ checks. The brute force ignores the order: it would do the same work on a shuffled array.