Galloping Search

Galloping search extends exponential search by starting from a known position instead of the beginning of the array. It is designed for scenarios where you already have a nearby index and want to locate a target relative to that position.

This technique appears in merge algorithms such as Timsort, where one run advances quickly into another.

Problem

Given a sorted array $A$, a starting index $s$, and a target $x$, find an index $i$ such that

$$ A[i] = x $$

If no such index exists, return $-1$.

Key Idea

Instead of scanning linearly from $s$, expand outward exponentially:

• Check positions $s + 1, s + 2, s + 4, s + 8, \dots$
• Stop when the value exceeds the target or bounds are reached

This identifies a bounded interval. Then apply binary search within that interval.

Algorithm

galloping_search(A, x, s):
    n = length(A)

    if A[s] == x:
        return s

    # forward gallop
    i = 1
    while s + i < n and A[s + i] <= x:
        i = i * 2

    l = s + i // 2
    r = min(s + i, n - 1)

    return binary_search(A, x, l, r)

Binary search:

binary_search(A, x, l, r):
    while l <= r:
        m = l + (r - l) // 2
        if A[m] == x:
            return m
        elif A[m] < x:
            l = m + 1
        else:
            r = m - 1
    return -1

Example

Let

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

Start at

$$ s = 2 \quad (A[s] = 5) $$

Search for

$$ x = 11 $$

Galloping phase:

step	offset	index	value
1	1	3	7
2	2	4	9
3	4	6	13

Now search in range $[4, 6]$. Binary search finds index $5$.

Correctness

The exponential phase guarantees:

• The target lies within the interval $[s + 2^{k-1}, s + 2^k]$ if it exists
• The interval contains all possible positions of $x$ beyond $s$

Binary search then finds the exact index inside this interval.

Complexity

Let $d$ be the distance from $s$ to the target.

phase	cost
galloping	$O(\log d)$
binary search	$O(\log d)$
total	$O(\log d)$

Worst case:

$$ O(\log n) $$

Space:

$$ O(1) $$

Variants

• Backward galloping: search left from $s$
• Bidirectional galloping: expand both directions
• Used in merging sorted runs

Use Cases

• Merging two sorted arrays efficiently
• Searching near a known position
• Adaptive algorithms like Timsort
• Sparse or clustered data

Implementation

def galloping_search(a, x, s):
    n = len(a)
    if a[s] == x:
        return s

    i = 1
    while s + i < n and a[s + i] <= x:
        i *= 2

    l = s + i // 2
    r = min(s + i, n - 1)

    while l <= r:
        m = l + (r - l) // 2
        if a[m] == x:
            return m
        elif a[m] < x:
            l = m + 1
        else:
            r = m - 1

    return -1

func GallopingSearch(a []int, x int, s int) int {
    n := len(a)
    if a[s] == x {
        return s
    }

    i := 1
    for s+i < n && a[s+i] <= x {
        i *= 2
    }

    l := s + i/2
    r := s + i
    if r >= n {
        r = n - 1
    }

    for l <= r {
        m := l + (r-l)/2
        if a[m] == x {
            return m
        } else if a[m] < x {
            l = m + 1
        } else {
            r = m - 1
        }
    }

    return -1
}