# 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:

$$
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

```text id="gis01"
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:

```text id="gis02"
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

```python id="gis03"
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
```

```go id="gis04"
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
}
```