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:

A \cap B

Idea

Maintain two indices $i$ and $j$ for arrays $A$ and $B$ .

If $A[i] = B[j]$ , record the match and advance both.
If $A[i] < B[j]$ , advance $i$ using exponential search to find the first position where $A[i] \ge B[j]$ .
If $A[i] > B[j]$ , advance $j$ symmetrically.

This avoids scanning every element when one array skips ahead quickly.

Algorithm

galloping_intersection(A, B):
    i = 0
    j = 0
    result = []

    while i < length(A) and j < length(B):
        if A[i] == B[j]:
            append result, A[i]
            i = i + 1
            j = j + 1

        elif A[i] < B[j]:
            i = gallop_forward(A, i, B[j])

        else:
            j = gallop_forward(B, j, A[i])

    return result

The galloping step:

gallop_forward(A, start, target):
    step = 1
    i = start

    while i + step < length(A) and A[i + step] < target:
        step = step * 2

    left = i + step // 2
    right = min(i + step, length(A) - 1)

    return lower_bound(A, target, left, right)

Example

Let

A = [1, 3, 5, 7, 9, 11, 13]

B = [2, 3, 6, 9, 10, 13]

Trace:

step	A[i]	B[j]	action
1	1	2	gallop A to ≥ 2 → i = 1
2	3	2	gallop B to ≥ 3 → j = 1
3	3	3	match → add 3
4	5	6	gallop A to ≥ 6 → i = 3
5	7	6	gallop B to ≥ 7 → j = 3
6	7	9	gallop A to ≥ 9 → i = 4
7	9	9	match → add 9
8	11	10	gallop B to ≥ 11 → j = 5
9	11	13	gallop A to ≥ 13 → i = 6
10	13	13	match → add 13

Result:

[3, 9, 13]

Correctness

At each step, elements strictly smaller than the current target are skipped. The exponential phase finds an interval that contains the first possible match, and the binary search refines it exactly.

Because both arrays are sorted, no candidate intersection element is skipped. Every match is detected when both pointers align at equal values.

Complexity

Let $n = |A|$ and $m = |B|$ .

case	time
balanced sizes	$O(n + m)$
highly unbalanced	$O(m \log(n/m))$ (assuming $n \gg m$ )

The galloping step reduces work when one array is much larger.

Space:

O(1)

excluding output.

When to Use

Use galloping intersection search when:

both inputs are sorted
one array may be much larger than the other
data is sparse or unevenly distributed
intersection queries are frequent

It is widely used in search engines, inverted index processing, and database query execution.

Implementation

import bisect

def gallop_forward(a, start, target):
    step = 1
    i = start
    n = len(a)

    while i + step < n and a[i + step] < target:
        step *= 2

    left = i + step // 2
    right = min(i + step, n - 1)

    return bisect.bisect_left(a, target, left, right + 1)

def galloping_intersection(a, b):
    i = j = 0
    result = []

    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            result.append(a[i])
            i += 1
            j += 1
        elif a[i] < b[j]:
            i = gallop_forward(a, i, b[j])
        else:
            j = gallop_forward(b, j, a[i])

    return result

func lowerBoundRange(a []int, x int, left int, right int) int {
    for left < right {
        mid := (left + right) / 2
        if a[mid] < x {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

func gallopForward(a []int, start int, target int) int {
    step := 1
    i := start
    n := len(a)

    for i+step < n && a[i+step] < target {
        step *= 2
    }

    left := i + step/2
    right := i + step
    if right >= n {
        right = n - 1
    }

    return lowerBoundRange(a, target, left, right+1)
}

func GallopingIntersection(a []int, b []int) []int {
    i, j := 0, 0
    result := []int{}

    for i < len(a) && j < len(b) {
        if a[i] == b[j] {
            result = append(result, a[i])
            i++
            j++
        } else if a[i] < b[j] {
            i = gallopForward(a, i, b[j])
        } else {
            j = gallopForward(b, j, a[i])
        }
    }

    return result
}