# Galloping Search

# 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

```id="gal-1"
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:

```id="gal-2"
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

```id="py-gal"
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
```

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