#merge-like

Galloping Intersection Search

Galloping Intersection Search Galloping intersection search computes the intersection of two sorted sequences by combining linear scanning with exponential jumps. When one sequence advances much faster than the other, the algorithm uses exponential search to skip ahead, then refines with binary search. This reduces unnecessary comparisons when the sequences differ significantly in size or distribution. Problem Given two sorted arrays $A$ and $B$, compute all elements that appear in both:...