Must the number of elements be a perfect square?

No. Choose a nearby positive integer block size and handle the final partial block correctly.

Is jump search a constant-space method?

A basic array implementation needs only a few indices and values beyond the input, so its auxiliary space can be constant.

Can there be several levels of jumps?

Yes. Research explores multi-level and variable-size variants; their analysis differs from the basic single-level procedure.

AI Glossary / Graphs and symbolic AI / Intermediate

Jump search

Definition

Jump search is a lookup algorithm for sorted data that checks spaced block boundaries until it locates the block that could contain a target, then searches within that block sequentially. It is also called block search.

What it means

The algorithm uses sorted order to skip blocks whose largest value is still below the target. Once a boundary reaches or exceeds the target, the answer, if present, lies in the corresponding candidate block.

This is different from binary search, which repeatedly halves the remaining interval. It also differs from interpolation search, which estimates a position from the target's numerical value. Basic jump search uses a selected block size rather than a value-based estimate.

The similarly named jump point search is a grid-pathfinding technique and solves another problem. In jump search, the jump is between positions in an ordered collection, not a route between locations on a map.

How it works

Choose a positive block size m and inspect the last element of the first block. If that value is less than the target, inspect the next block's last element, continuing until the target could fall in the current block or the collection is exhausted.

Scan the candidate block in order. Return a matching position if found. Stop with absence when a scanned value exceeds the target or the candidate block ends without a match. The final block may be shorter than m, so boundary indices must be limited to the actual array length.

Empty arrays, duplicate values and targets outside the overall range need a clear interface. If duplicates occur, specify whether any match, the first match or all matches are required. The usual basic algorithm and comparison count do not automatically satisfy every such return policy.

Three practical examples

An algorithm lesson compares block-boundary probing with a full linear scan on a sorted array.
A storage experiment studies lookup when blocks can be accessed efficiently but repeated arbitrary midpoint access is unattractive.
A software review tests whether a lookup routine handles a short final block without reading beyond the collection.

Think of it this way

Think of checking the last listed surname on every few pages of an alphabetized directory. Once a page boundary passes the target surname, inspect the entries in that section closely.

The analogy explains coarse location followed by a local scan. Its usefulness depends on the ability to reach the sampled boundaries efficiently; a jump is not free merely because the algorithm names it one.

Worked example

Finding a target in a four-item block

Take the sorted array [3, 7, 11, 14, 18, 22, 27, 31, 36, 42, 47, 53, 60, 68, 75, 84], indexed from 0 to 15. Choose block size 4 and search for 47.

The first boundary is index 3, with value 14. Because 14 is below 47, skip the first block. The next boundary is index 7, with value 31, so skip the second block. The third boundary is index 11, with value 53, which is above 47. The candidate block is therefore indices 8 through 11.

Scan that block from its beginning: index 8 contains 36, index 9 contains 42 and index 10 contains 47. The search succeeds at index 10. Under this boundary-then-scan convention, it made three boundary comparisons and three scan comparisons, totaling six. A linear scan from index zero would examine eleven entries before finding the same target.

For missing target 46, the same boundaries identify the same block. Scanning reaches 47, which exceeds 46, so absence is established. The routine should not report 47 as a match.

This small comparison does not establish that jump search beats binary search or has lower elapsed time. It isolates the mechanism and uses an explicit counting convention; implementations can avoid repeating a boundary comparison already performed.

Illustrative case study

The fictional Cedar Lookup team evaluates a block-based search routine on ordered records. Its initial tests cover only targets located exactly at block boundaries.

Reviewers add targets inside blocks, absent values between neighboring keys and a collection whose length is not divisible by the block size. They verify returned positions against a straightforward scan and measure actual access cost separately from the number of key comparisons.

Cedar also checks whether the storage layout really allows efficient boundary access. This fictional case demonstrates why a correct array-level comparison count is only part of a practical performance assessment. It does not report a production speedup.

Common misconceptions and mistakes

Jump search works correctly on arbitrary unsorted data. Skipping blocks relies on sorted order.
A block-boundary value above the target proves absence. The target may occur earlier within that block.
The square-root block size is optimal under every storage model. Different access costs or variants can change the preferred size.
Fewer comparisons always means less runtime. Reaching boundaries and reading blocks also have costs.

Business use

For n entries and block size m, the basic worst-case comparison work is on the order of n/m + m: boundary probes plus a local scan. Balancing these terms gives a block size near the square root of n and O(square root of n) comparisons under the simple model.

Binary search has a better logarithmic comparison bound when efficient random access is available. Jump search is useful for understanding access-pattern tradeoffs and for settings whose storage constraints favor block-oriented or sequential access. If reaching each nominal jump requires traversing every intervening linked-list element, the traversal work can remain linear even though fewer keys are compared.

Check your understanding

Why does finding boundary value 53 not end the search for 47?

Answer: It identifies a block whose earlier entries may contain 47. The algorithm must inspect that block rather than treating the boundary as the only possible match.

Related terms

Linear search
Binary search
Interpolation search
Sorted array
block search
comparison complexity
random access
search key

Learn next

Repeat the worked search with block size 2 and then 8, using the same comparison-count convention. Explain how fewer boundary checks can be offset by more scanning within a larger block.

Sources

NIST defines basic jump search and its square-root block-size rule: https://xlinux.nist.gov/dads/HTML/jumpsearch.html

Shneiderman's original paper analyzes variants and different access costs: https://www.cs.umd.edu/~ben/papers/Shneiderman1978Jump.pdf

NIST describes the binary-search comparison: https://xlinux.nist.gov/dads/HTML/binarySearch.html

The sixteen-entry array and Cedar Lookup case are original illustrations. Comparison counts are distinguished from physical data-access costs.

Previous: Jump point search Next: Junction tree algorithm