concept · INFO-CS-ADS-122Jump Search
Jump search locates an element in a sorted array by moving forward in fixed-size blocks and then performing a linear search inside the block that may contain the target.
Explanation
Overview
Jump search is a searching algorithm for sorted arrays that checks selected elements at regular intervals. When a checked value reaches or exceeds the target, the algorithm searches linearly within the preceding block.
Purpose
Its purpose is to reduce the number of element accesses compared with a full linear scan while using a simpler block-based strategy than binary search.
Working principle
Instead of examining every element, the algorithm jumps forward by a fixed block size. Once it finds a block whose last checked value is at least the target, it searches sequentially within that block.
Key concepts
name: Core idea; description: The central focus of jump search is the capability described here: Jump search locates an element in a sorted array by moving forward in fixed-size blocks and then performing a linear search inside the block that may contain the target.; name: Problem context; description: Jump Search is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using jump search, check its assumptions, input requirements, expected output, and resource constraints.
Space complexity
O(1) auxiliary space for the standard iterative implementation.
Example
For the sorted array [2, 5, 8, 12, 16, 20, 24, 28, 32] and target 24, a jump size of 3 checks block-ending values and identifies the block containing 24. It then performs a short linear scan inside that block.
Pseudocode
JUMP_SEARCH(A, target):
n = length(A)
step = floor(sqrt(n))
start = 0
end = step
while start < n and A[min(end, n) - 1] < target:
start = end
end = end + step
if start >= n:
return -1
for i = start to min(end, n) - 1:
if A[i] == target:
return i
if A[i] > target:
return -1
return -1
Example or application
For the sorted array [2, 5, 8, 12, 16, 20, 24, 28, 32] and target 24, a jump size of 3 checks block-ending values and identifies the block containing 24. It then performs a short linear scan inside that block.
Definition
Jump search is a searching algorithm for sorted arrays that checks selected elements at regular intervals. When a checked value reaches or exceeds the target, the algorithm searches linearly within the preceding block.
Purpose
Its purpose is to reduce the number of element accesses compared with a full linear scan while using a simpler block-based strategy than binary search.
Prerequisites
The collection must be sorted according to the comparison rule. The standard algorithm is designed for arrays that support efficient indexed access.
Working Principle
Instead of examining every element, the algorithm jumps forward by a fixed block size. Once it finds a block whose last checked value is at least the target, it searches sequentially within that block.
Block Size
A common choice for the block size is approximately the square root of the number of elements, written as √n. This balances the number of jumps with the amount of linear searching required.
Algorithm Steps
Determine the number of elements in the array.
Choose a jump size, commonly the square root of the array length.
Start at the first block boundary.
Jump forward while the checked element is smaller than the target.
Identify the block in which the target may exist.
Perform a linear search inside that block.
Return the matching index or report that the target is absent.
Pseudocode
JUMP_SEARCH(A, target):
n = length(A)
step = floor(sqrt(n))
start = 0
end = step
while start < n and A[min(end, n) - 1] < target:
start = end
end = end + step
if start >= n:
return -1
for i = start to min(end, n) - 1:
if A[i] == target:
return i
if A[i] > target:
return -1
return -1
Best Case
O(1) time when the target is found at an element examined immediately by the initial checks.
Average Case
O(√n) comparisons under the usual assumptions for a sorted array and a block size proportional to √n.
Worst Case
O(√n) time when using a block size near √n, because the algorithm performs approximately √n jumps followed by a linear scan of at most approximately √n elements.
Space Complexity
O(1) auxiliary space for the standard iterative implementation.
Block Size Tradeoff
A larger block size reduces the number of jumps but increases the maximum linear scan within a block. A smaller block size has the opposite effect. A size near √n balances these costs.
Advantages
Can require fewer comparisons than linear search on large sorted arrays.
Uses constant auxiliary space.
Has a straightforward block-based implementation.
Does not require recursive calls.
Can be useful when block-level access is convenient.
Limitations
Requires sorted data.
Usually performs more comparisons than binary search on random-access arrays.
Needs an appropriate block-size choice.
Is not well suited to linked lists if the implementation relies on repeated indexed access.
Comparison With Linear Search
Linear search examines each element sequentially. Jump search skips groups of elements and only scans sequentially inside the block that may contain the target.
Comparison With Binary Search
Binary search repeatedly halves the candidate interval and takes O(log n) time. Jump search uses blocks and takes O(√n) time with the usual block-size choice, so binary search is generally more efficient for ordinary array lookup.
Practical Applications
Searching in sorted arrays where a simple block-based method is desired.
Educational demonstrations of block searching.
Situations where sequential scanning within a selected block is convenient.
Implementation Considerations
The final block may contain fewer elements than the chosen jump size. Boundary calculations must avoid accessing an index outside the array, and the linear scan should stop when the current value exceeds the target.
Common Errors
Applying jump search to unsorted data.
Choosing a block size without considering the collection length.
Accessing an element beyond the final array index.
Failing to search the block in which the target may exist.
Continuing a linear scan after the current value has exceeded the target.
Key Takeaway
Jump search combines block-level jumps with a short linear scan. Its typical O(√n) performance makes it an improvement over linear search in suitable cases, although binary search is usually faster on sorted arrays.
Key Concepts
| Name | Description |
|---|
Core idea | The central focus of jump search is the capability described here: Jump search locates an element in a sorted array by moving forward in fixed-size blocks and then performing a linear search inside the block that may contain the target. |
Problem context | Jump Search is relevant when a computational task requires the behavior or capability described by this topic. |
Correct use | Before using jump search, check its assumptions, input requirements, expected output, and resource constraints. |
Practice Questions
| Question | Answer |
|---|
What is the main purpose of jump search? | Jump search locates an element in a sorted array by moving forward in fixed-size blocks and then performing a linear search inside the block that may contain the target. |
What should be checked before applying jump search? | For jump search, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints. |
How can an implementation of jump search be validated? | Trace a representative jump search case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline. |
Learning Objectives
Explain the central idea and purpose of jump search.
Identify the assumptions, inputs, and conditions relevant to jump search.
Evaluate an application of jump search for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Scienexy Computer Science Reference
Suggest a correction or source · More in Algorithms & Data Structures