Jump Search is a searching algorithm designed to work on sorted arrays. Unlike Linear Search, which checks each element one by one, or Binary Search, which divides the array in half each time, Jump Search moves in fixed-size steps or “jumps” to quickly find the target. When it overshoots the target, it performs a linear search within the last block. This approach can be faster than linear search while being simpler than binary search in some scenarios.
with hands-on learning.
get the skills and confidence to land your next move.
For beginners learning Rust, Jump Search is a practical algorithm to understand how to combine loops, arithmetic, and conditional logic. It is especially useful for large sorted arrays where checking every element would be inefficient, such as in indexed datasets or sorted numeric records. Learning this algorithm also helps programmers think about balancing step size with efficiency.
Program 1: Iterative Jump Search on Integers
This program demonstrates Jump Search on a sorted array of integers using a loop. It calculates the optimal jump size and searches in blocks.
fn jump_search(arr: &[i32], target: i32) -> Option<usize> {
let n = arr.len();
let step = (n as f64).sqrt() as usize;
let mut prev = 0;
let mut curr = step;
while curr < n && arr[curr - 1] < target {
prev = curr;
curr += step;
}
let end = if curr < n { curr } else { n };
for i in prev..end {
if arr[i] == target {
return Some(i);
}
}
None
}
fn main() {
let numbers = [10, 20, 30, 40, 50, 60, 70];
let target = 40;
println!("Array: {:?}", numbers);
match jump_search(&numbers, target) {
Some(idx) => println!("Element {} found at index {}", target, idx),
None => println!("Element {} not found", target),
}
}In this example, the array is divided into blocks of size √n. Jumping quickly over blocks helps reduce comparisons, and the linear search inside the block ensures accuracy. Beginners can see how math and loops combine to optimize searching.
Program 2: Jump Search Using Recursive Block Search
Recursion can also implement Jump Search by searching within blocks until the target is found.
fn jump_search_recursive(arr: &[i32], target: i32, prev: usize, step: usize) -> Option<usize> {
if prev >= arr.len() {
return None;
}
let curr = if prev + step < arr.len() { prev + step } else { arr.len() };
if arr[curr - 1] >= target {
for i in prev..curr {
if arr[i] == target {
return Some(i);
}
}
return None;
}
jump_search_recursive(arr, target, curr, step)
}
fn main() {
let numbers = [5, 15, 25, 35, 45, 55];
let target = 35;
let step = (numbers.len() as f64).sqrt() as usize;
println!("Array: {:?}", numbers);
match jump_search_recursive(&numbers, target, 0, step) {
Some(idx) => println!("Element {} found at index {}", target, idx),
None => println!("Element {} not found", target),
}
}Recursion offers a clean way to handle block searching. Beginners can trace the recursive calls to understand how Jump Search narrows down the search area progressively.
Program 3: Jump Search with Debug Statements
Debugging can make it easier to visualize how the algorithm jumps over blocks and performs linear search.
fn jump_search_debug(arr: &[i32], target: i32) -> Option<usize> {
let n = arr.len();
let step = (n as f64).sqrt() as usize;
let mut prev = 0;
let mut curr = step;
while curr < n && arr[curr - 1] < target {
println!("Jumping from index {} to {}", prev, curr);
prev = curr;
curr += step;
}
let end = if curr < n { curr } else { n };
for i in prev..end {
println!("Checking index {}: value {}", i, arr[i]);
if arr[i] == target {
return Some(i);
}
}
None
}
fn main() {
let numbers = [2, 4, 6, 8, 10, 12];
let target = 10;
println!("Array: {:?}", numbers);
match jump_search_debug(&numbers, target) {
Some(idx) => println!("Element {} found at index {}", target, idx),
None => println!("Element {} not found", target),
}
}This approach helps beginners understand how jumps reduce the number of comparisons and how linear search inside the block ensures correctness.
Program 4: Jump Search for Floating-Point Numbers
Jump Search can also work with decimal numbers. This example shows a sorted array of floats.
fn jump_search_floats(arr: &[f64], target: f64) -> Option<usize> {
let n = arr.len();
let step = (n as f64).sqrt() as usize;
let mut prev = 0;
let mut curr = step;
while curr < n && arr[curr - 1] < target {
prev = curr;
curr += step;
}
let end = if curr < n { curr } else { n };
for i in prev..end {
if (arr[i] - target).abs() < std::f64::EPSILON {
return Some(i);
}
}
None
}
fn main() {
let numbers = [1.1, 2.5, 3.2, 4.7, 5.9];
let target = 3.2;
println!("Array: {:?}", numbers);
match jump_search_floats(&numbers, target) {
Some(idx) => println!("Element {} found at index {}", target, idx),
None => println!("Element {} not found", target),
}
}Handling floats requires careful comparison using small thresholds. Beginners learn to adapt integer algorithms for real numbers while maintaining efficiency.
Program 5: Jump Search with Early Exit Optimization
This version quickly exits if the target is outside the possible range, saving unnecessary calculations.
fn jump_search_early_exit(arr: &[i32], target: i32) -> Option<usize> {
let n = arr.len();
if n == 0 || target < arr[0] || target > arr[n - 1] {
return None;
}
let step = (n as f64).sqrt() as usize;
let mut prev = 0;
let mut curr = step;
while curr < n && arr[curr - 1] < target {
prev = curr;
curr += step;
}
let end = if curr < n { curr } else { n };
for i in prev..end {
if arr[i] == target {
return Some(i);
}
}
None
}
fn main() {
let numbers = [100, 200, 300, 400, 500];
let target = 50;
println!("Array: {:?}", numbers);
match jump_search_early_exit(&numbers, target) {
Some(idx) => println!("Element {} found at index {}", target, idx),
None => println!("Element {} not found", target),
}
}Early exit improves efficiency, especially when the target is clearly out of range. Beginners can see how simple checks enhance algorithm performance.
Frequently Asked Questions (FAQ)
Q1: What is the time complexity of Jump Search?
The time complexity is O(√n), with n being the number of elements.
Q2: Can Jump Search work on unsorted arrays?
No, the array must be sorted for it to function correctly.
Q3: How do I choose the jump size?
The optimal jump size is generally the square root of the array length (√n).
Q4: Is Jump Search faster than Binary Search?
It can be faster for small or uniformly distributed arrays, but Binary Search usually performs better on large datasets.
Q5: Can Jump Search handle floats?
Yes, with careful handling of floating-point comparisons.
Conclusion
Jump Search is an efficient and beginner-friendly searching algorithm for sorted arrays. By moving in jumps and performing small linear searches within blocks, it reduces unnecessary comparisons while remaining easy to understand. Rust implementations demonstrate both iterative and recursive approaches, as well as optimizations for early exits and floats. Practicing Jump Search helps beginners understand array traversal, conditional logic, and algorithm efficiency.
