Finger Search, in depth: galloping, O(log d) searches, near-optimal intersections, level-linked trees and skip-list fingers

The idea: pay for distance, not size

Let the data be a sorted sequence of n keys and the finger a position f whose key you know. For a query x, let d be the number of positions between f and the place x belongs. A finger search finds that place in O(log d) comparisons, and with d near n it is within a constant factor of ordinary binary search, so it is a safe choice whenever queries have locality.

Locality compounds. Run m queries in sorted order, leaving the finger where each one ended. The cost is the sum of log(d_i + 1), and because the d_i add up to at most n, concavity of the logarithm bounds the total by m log(n/m + 1). For m = 1 that is a binary search, for m = n it is a linear scan, and in between it beats both. That one inequality is why finger search shows up inside merging, set intersection, adaptive sorting and range scans.

Galloping search on a sorted array

On an array the finger is just an index and the search has two phases. First gallop: probe f, f + 1, f + 2, f + 4, f + 8 and so on, doubling the step until a probe reaches a key at least x or runs off the end. If the target is d places away, that takes about log2 d probes. Then binary search inside the last bracket, whose width is also about d, for another log2 d. Total: about 2 log2 d comparisons.

def finger_search(a, f, x):
    # Smallest i >= f with a[i] >= x. Precondition: f == 0 or a[f - 1] < x.
    n, step, lo, hi = len(a), 1, f, f
    while hi < n and a[hi] < x:      # gallop: probe f, f+1, f+2, f+4, ...
        lo = hi + 1
        hi = f + step
        step *= 2
    hi = min(hi, n)
    while lo < hi:                   # binary search in [lo, hi)
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

The invariant is that a[lo - 1] < x (that index was probed or lies before the finger) and that a[hi] >= x or hi == n. Measured on a sorted array of one million even integers with the finger at index 500, counting every key comparison:

A plain binary search over the same array needs 20 comparisons for any target. Galloping is ahead below roughly d = 1,000 and behind above it; the break-even is where 2 log2 d = log2 n, which is d = √n. So galloping is a bet on locality, and when the bet is wrong it loses by at most about a factor of two. That is why TimSort, the sort used by CPython and for Java object arrays, enters a galloping mode during merges only after one run has won several comparisons in a row: it waits for evidence of locality before betting on it. The mergesort article covers that merge loop.

Worked example: intersecting a short list with a long one

Take A with 1,000 sorted keys and B with 1,000,000, both sampled without replacement from 0 to 10 million (seed 2), and compute their intersection. The textbook two-pointer merge advances through both lists and takes 1,000,680 steps. Galloping through B with a finger that only moves forward does one finger search per element of A:

def intersect(A, B):
    # A is the short list; both sorted ascending
    out, f = [], 0
    for x in A:
        f = finger_search(B, f, x)   # precondition holds: B[f - 1] < previous x <= x
        if f == len(B):
            break
        if B[f] == x:
            out.append(x)
    return out

It found the same 94 common keys with 20,452 comparisons, about 49 times fewer. There is a floor: any comparison-based merge of m sorted keys into n must distinguish log2 C(m + n, m) possible interleavings, about 11,403 here, which is roughly m log2(n/m) + 1.44m. Galloping lands within a factor of two of that floor, as the 2 log d analysis predicts, without knowing m or n in advance. The two-pointer merge is optimal only when the lists have similar sizes.

The same shape appears in inverted-index query processing, where a rare term's short posting list meets a common term's long one, in sort-merge joins with skewed inputs, and in folding a small batch of updates into a large sorted run. When the long side lives on disk, each probe can be a random read while the merge reads sequentially, so compare page reads on the real storage rather than comparison counts alone.

Finger search in balanced trees

Arrays are static. For a sorted set that changes, the finger must live in a balanced tree, and an ordinary binary search tree is not enough. Walking up from the finger's node to the lowest common ancestor of finger and target looks like O(log d), but two adjacent keys can sit on opposite sides of the root, so the climb can cost log n even when d = 1.

Level-linked trees fix that. In a level-linked 2-3 tree or B-tree, every node also points to its left and right neighbours on the same level. The search climbs from the finger's leaf; at each level it checks whether x lies within the current node's range or its neighbour's in the direction of x, and as soon as it does, it descends. Climbing k levels means the range covered has grown to at least 2^k keys, so the climb stops after O(log d) levels and the descent costs the same. Huddleston and Mehlhorn showed that in such trees, built on (a, b)-trees with b at least 2a, an insertion or deletion at the finger costs O(1) amortised rebalancing once its position is known, so bursts of updates near the finger stay cheap.

finger_search(finger_leaf, x):
    node = finger_leaf
    while node is not root and not covers(node, x):
        nb = node.right if x > node.max_key else node.left    # level link
        if nb is not None and covers(nb, x):
            node = nb
            break
        node = node.parent
    while not node.is_leaf:          # ordinary descent from here
        node = child_containing(node, x)
    return node

In a B+tree, sibling links between leaves turn a range-scan cursor into a finger search with d = 1 per step. Whether a new seek near the cursor reuses its path or restarts at the root depends on the engine, so check yours if your workload is "seek near the last position"; the B-tree deep dive covers the node layout these decisions depend on.

Skip lists with a finger

A skip list keeps keys in a sorted linked list with randomly promoted express lanes. Its natural finger is the update vector: for each level, the last node at that level whose key is below the previous search key. A forward finger search climbs while the next node one level up is still before x, then descends in the ordinary way, refreshing the vector as it goes:

def skip_finger_search(finger, x):
    # finger[k]: last node at level k with key < previous target; requires x >= that target
    level = 0
    while level + 1 < len(finger):
        nxt = finger[level + 1].next[level + 1]
        if nxt is None or nxt.key >= x:
            break
        level += 1                   # target is far: use a faster lane
    node = finger[level]
    for k in range(level, -1, -1):
        while node.next[k] is not None and node.next[k].key < x:
            node = node.next[k]
        finger[k] = node             # levels above `level` are still valid
    return node.next[0]

With promotion probability one half, nodes at level k are about 2^k keys apart, so the climb stops after about log2 d levels and the descent takes a constant expected number of steps per level: expected O(log d) per search. The vector stays valid across inserts because an insert computes exactly this vector anyway. The skip list article covers the base structure and its concurrent variants.

Splay trees: a finger without a finger

A splay tree keeps no explicit finger yet behaves as if it had one. Each access rotates the accessed node to the root, so the previous target is always where the next search starts. Cole's dynamic finger theorem (2000) bounds a sequence of accesses by O(n + m) plus the sum of log(d_i + 1), where d_i is the rank distance between consecutive accesses. Sequential access is the extreme case: O(1) amortised per step. The price is that every access, even a read, rewrites pointers, which is hostile to caches and to concurrent readers. The splay tree article covers the rotations and the amortised analysis.

Finger trees are a different thing

The name collides with a well-known functional data structure. A 2-3 finger tree, described by Hinze and Paterson, is a persistent sequence with amortised O(1) access at both ends and logarithmic split and concatenation, parameterised by a monoid so the same skeleton becomes a deque, a priority queue or an indexed sequence; Haskell's Data.Sequence is built on one. Its fingers are fixed at the two ends. It does not give O(log d) search from an arbitrary moving position. If a design document says "finger tree", check which meaning is intended before choosing a library.

Where the finger lives in a system

In a running system the finger is state, owned by whatever iterates: a merge loop, a cursor, a sweep. It helps to name where it lives and what distance to expect:

A finger belongs to one consumer, and it must be revalidated whenever the structure changes underneath it.

Failure modes

• Stale fingers. An insert, delete or rebalance can move or free the node a finger points at; library iterators are invalidated by structural changes for this reason. Tag each finger with a version counter and fall back to a root search on mismatch.
• Wrong direction. The array code searches forward only and assumes a[f - 1] < x. A query behind the finger silently returns f. Check the direction and gallop backwards when needed, or assert the precondition.
• No locality. With random queries, galloping does about 2 log2 n comparisons, twice a binary search. Measure the distribution of d first, or gallop only after recent queries were close together, as TimSort does.
• Overflow. With fixed-width integers, f + step can overflow on huge arrays. Cap the step by the remaining length before adding.
• Duplicates. Decide whether the search returns the first key at least x or the first key greater than x, and keep the finger consistent; mixing them in a merge drops or duplicates equal keys.
• Concurrency. A finger into a structure another thread mutates needs the same protection as any pointer: a lock, an epoch scheme or optimistic validation.

Trade-offs

If the data is mostly static and queries arrive in batches, sort the batch and gallop through an array; nothing beats its constants. If updates cluster near a moving position, a skip list or level-linked tree pays for its extra pointers. A splay tree suits single-threaded workloads with strong locality and no other structure to exploit.

What to do next

1. Log the rank distance between consecutive queries on your hot path. If the median is far below √n, galloping pays.
2. Replace two-pointer merges of very unequal lists with intersect, and keep the two-pointer version as a test oracle on random inputs.
3. Assert the finger precondition and handle backward queries explicitly.
4. For mutable sets, use a structure with real fingers, a skip-list update vector or a level-linked tree, rather than a cached pointer into a plain BST.
5. Version every finger and fall back to a root search on mismatch.
6. Benchmark on the real storage: when a probe is a page read, compare probe counts with the cost of a sequential scan.