Jump Search

Jump search (also known as block search) is a deterministic comparison-based search algorithm within computation and algorithms designed to locate a target value x inside an n-element sorted array A[0 .. n − 1] by partitioning the table into fixed-width blocks of size m. Formalized and analyzed by Ben Shneiderman in 1978 in Communications of the ACM, the algorithm operates as a two-level index scan: in the first phase, it steps forward through the array at regular index multiples 0, m, 2m, 3m, … until encountering a block boundary A[min((k + 1)m, n) − 1] ≥ x; in the second phase, it executes a sequential linear scan across the bracketed subarray [k · m, min((k + 1)m, n) − 1] to identify the precise match or insertion position.

By choosing the block stride m = ⌊√n⌋, jump search balances the number of coarse block jumps against the length of the subsequent intra-block linear scan, reducing the worst-case number of comparisons from n (for sequential linear search) down to at most ⌊n / m⌋ + (m − 1) ≈ 2√n − 1 = O(√n) while requiring O(1) auxiliary memory. Although its asymptotic comparison count Θ(√n) is larger than the Θ(log n) bound of divide-and-conquer binary search or exponential search, jump search traverses the array monotonically in the forward direction (performing at most one backward seek to the start of the final candidate block) and serves as the foundational one-dimensional model for multi-level ISAM index structures and skip list towers.

Forward Stride Phase and Intra-Block Linear Scan

Let A[0 .. n − 1] be a sorted array satisfying A[0] ≤ A[1] ≤ … ≤ A[n − 1], let x be the target search key, and let m ∈ {1, 2, …, n} denote a fixed block stride. Standard two-level jump search proceeds through two deterministic stages:

1. Coarse jumping phase (level-1 stride): Maintain a previous block start index prev ← 0 and an active block boundary step ← m. While A[min(step, n) − 1] < x, advance the window by setting prev ← step and step ← step + m. If prev ≥ n, the target x exceeds every element in the array and the search terminates unsuccessfully.
2. Fine linear scan phase (level-0 scan): Once the coarse phase halts, the target key x—if present in A—is guaranteed by sortedness to reside within the half-open index interval [prev, min(step, n)). The algorithm steps sequentially through j = prev, prev + 1, …, min(step, n) − 1 while A[j] < x.
3. Termination test: If the inner scan halts at an index j < min(step, n) where A[j] = x, return j; otherwise return not found (with j as the sorted insertion rank).

In Shneiderman's alternative backward-scan formulation, the coarse phase directly tests indices m − 1, 2m − 1, 3m − 1, … until A[k · m − 1] ≥ x; if equality holds at the boundary, the search returns k · m − 1 at once, and if A[k · m − 1] > x, the fine phase scans backward from k · m − 2 down to (k − 1)m. Both variants examine at most m − 1 elements inside the candidate block after the boundary comparison.

Calculus Optimization of the Block Stride m

To determine the block size m that minimizes computational work, consider the worst-case number of key comparisons C_worst(m) when the target key resides at the very end of the last block (or just before the jump boundary of the final block):

where n / m counts the coarse boundary comparisons across all blocks and m − 1 counts the sequential element comparisons within the selected block. Treating m > 0 as a continuous real variable and differentiating C_worst(m) with respect to m yields:

Because the second derivative d²C_worst / dm² = 2n / m³ > 0 for all m > 0, the choice m^* = √n is the unique global minimum, yielding a worst-case comparison count of:

For an average successful search assuming all n array positions are equally likely to be queried, the coarse phase performs an average of (1 / 2)(n / m) jumps and the fine scan examines an average of (1 / 2)(m − 1) intra-block elements:

Differentiating C_avg(m) with respect to m gives −n / (2m²) + 1 / 2 = 0, which again selects the precise same optimal stride m^* = √n and yields an average comparison count of √n − 1/2.

Cost-Weighted Optimal Stride for Asymmetric Jump vs. Scan Costs

In physical storage hierarchies—such as magnetic tape drives, cylindrical disk tracks, or compressed columnar database blocks—a coarse jump across m records incurs a seek cost a that differs from the sequential element-scan cost b. Shneiderman (1978) modeled the total expected search cost under weighted step costs a and b as:

Setting dE / dm = −a · n / m² + b = 0 yields the cost-adjusted optimal block size:

When random jumps are expensive relative to sequential streaming (a ≫ b, as in prefetch-friendly L1/L2 CPU cache lines or rotational storage), the optimal block size m^* expands by the factor √(a / b), performing fewer coarse jumps and exploiting high-bandwidth sequential scans within each block.

Recursive k-Level Hierarchy

Rather than resolving the bracketed block of size m₁ via a flat linear scan, multi-level jump search recursively partitions each level's block using progressively finer strides m₁ > m₂ > … > m_k−1 > m_k = 1. In a k-level jump search over n sorted elements:

• Level 1 jumps by stride m₁ across the full array of size n, performing at most n / m₁ comparisons.
• Level 2 jumps by stride m₂ inside the bracketed block of size m₁, performing at most m₁ / m₂ comparisons.
• Level j jumps by stride m_j inside a sub-block of size m_j−1, performing at most m_j−1 / m_j comparisons.
• Level k performs a unit-stride linear scan (m_k = 1) of at most m_k−1 − 1 comparisons.

The worst-case comparison count across all k levels is the sum:

By the arithmetic-mean–geometric-mean (AM–GM) inequality (or by setting all partial derivatives ∂C_worst / ∂m_j = 0 simultaneously), the sum is minimized when all k terms are equal:

Thus the optimal stride at level j is m_j^* = n^(k−j)/k for j = 1, 2, …, k, and the resulting worst-case comparison complexity of k-level jump search is:

Asymptotic Limit at k = log2 n

If the number of hierarchy levels k is itself allowed to grow with n, differentiating f(k) = k · n^1/k with respect to k gives:

which achieves its mathematical minimum at k = ln n (where the branching factor per level is n^1/k = e ≈ 2.718). Restricting the branching factor per level to the smallest integer n^1/k = 2 sets the number of levels to k = log₂ n, where each level's stride is m_j = n / 2^j. At each level j, testing a single midpoint boundary takes at most 2 − 1 = 1 comparison, reducing k-level jump search to standard binary search with worst-case bound:

Furthermore, materializing the k-level jump boundaries as explicit forward pointers attached to each element yields a deterministic multi-level linked index identical in geometry to a perfectly balanced skip list or a static B-tree directory.

Jump search remains practically relevant in three systems scenarios where standard binary search suffers architectural penalties:

1. Sequential and forward-only cursors: On singly linked lists equipped with express jump pointers, forward-only network streams, or magnetic tape archives where rewinding across half the medium is orders of magnitude slower than stepping forward, jump search tests A[prev + m] via lookahead before advancing the read head, completing the search with zero backward seeks.
2. CPU hardware prefetcher alignment: Standard binary search leaps across large, non-monotonic power-of-two strides (n/2, n/4, n/8, …) that defeat L1/L2 stream prefetchers and trigger translation lookaside buffer (TLB) misses on large arrays. A two- or three-level jump search whose innermost block fits inside a single 4-kilobyte OS page or 64-byte cache line allows the final scan to execute with vectorized SIMD comparisons (AVX-512 or NEON) at full memory-bus bandwidth.
3. Compressed posting lists and delta-encoded blocks: In inverted indexes where document IDs are stored using differential gap encoding (d1, d2 − d1, d3 − d2, …), random access to the midpoint is impossible without decoding from the start of the list. Storing explicit uncompressed synchronization values at every √n-th entry allows two-level jump search to skip over compressed blocks in O(√n) time with only O(√n) synchronization overhead.

Why is the optimal jump size √n instead of n / 2 or a fixed constant like 64?

If the jump size m is a fixed constant such as 64, the coarse phase must perform n / 64 jumps in the worst case, which still grows linearly as Θ(n) when n reaches millions of elements. Conversely, if the jump size is n / 2, the coarse phase performs only 2 jumps, but the subsequent linear scan inside the selected half must inspect up to n / 2 − 1 elements, again taking Θ(n) time. Setting m = √n equalizes the worst-case jump count (n / √n = √n) and the worst-case intra-block scan length (√n − 1), minimizing their sum at 2√n − 1.

How does jump search compare to exponential search?

Jump search steps outward by a constant additive stride m = √n (visiting indices m, 2m, 3m, …) and then finishes with a linear scan, requiring knowledge of n to set m = √n and taking Θ(√n) comparisons. Exponential search steps outward by multiplicative doubling (visiting indices 1, 2, 4, 8, …, 2^k) and finishes with a binary search, requiring no prior knowledge of n and completing in O(log i) comparisons where i is the target's index.

Can jump search be implemented with zero backward steps on a singly linked stream?

Yes. By holding a reference to the current block start prev while peeking ahead to the next block boundary next = prev + m, the algorithm compares the key at next against x before committing the cursor movement. As soon as the key at next is greater than or equal to x, the algorithm walks forward from prev one node at a time, never moving a pointer backward.

1. Shneiderman, B. (1978). "Jump searching: A fast sequential search technique." Communications of the ACM, 21(10), 831–834. https://doi.org/10.1145/359619.359623
2. Six, H.-W., & Wegner, L. (1984). "Sorting a random file in situ." The Computer Journal, 27(3), 270–275. https://doi.org/10.1093/comjnl/27.3.270
3. Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed., Section 6.2.1: "Searching an Ordered Table," pp. 409–426). Addison-Wesley. https://cs.stanford.edu/
4. Pugh, W. (1990). "Skip lists: A probabilistic alternative to balanced trees." Communications of the ACM, 33(6), 668–676. https://doi.org/10.1145/78973.78977