Searching for an element in a list is one of the most common tasks in programming. While Linear Search and Binary Search are often taught first, Jump Search offers an interesting alternative for sorted arrays. Jump Search improves efficiency by jumping ahead by fixed steps instead of checking every element one by one, combining the simplicity of Linear Search with some advantages of Binary Search.
with hands-on learning.
get the skills and confidence to land your next move.
Jump Search is particularly useful when you work with sorted datasets and want faster results than a basic Linear Search, without the overhead of recursion or complex divide-and-conquer logic. For beginners, learning Jump Search helps develop an understanding of step-wise searching and array traversal. It also introduces the concept of optimizing search performance by skipping unnecessary checks, which is a practical skill in real-world applications like searching in sorted lists, directories, or records.
Program 1: Basic Jump Search Using Loops
This program demonstrates a standard Jump Search using a fixed step to locate a target number in a sorted array.
<?php
$array = [1, 3, 5, 7, 9, 11, 13, 15];
$target = 9;
$length = count($array);
$step = floor(sqrt($length));
$prev = 0;
while ($array[min($step, $length) - 1] < $target) {
$prev = $step;
$step += floor(sqrt($length));
if ($prev >= $length) {
echo "Element $target not found.";
exit;
}
}
for ($i = $prev; $i < min($step, $length); $i++) {
if ($array[$i] == $target) {
echo "Element $target found at index $i.";
exit;
}
}
echo "Element $target not found.";
?>This program works by jumping ahead by the square root of the array length until the target is likely to be within a block, then performing a linear search within that block. Beginners can see how Jump Search reduces the number of comparisons while keeping the logic simple and easy to follow.
Program 2: Jump Search Wrapped in a Function
Encapsulating Jump Search in a function allows reuse for different arrays and target values.
<?php
function jumpSearch($arr, $target) {
$length = count($arr);
$step = floor(sqrt($length));
$prev = 0;
while ($arr[min($step, $length) - 1] < $target) {
$prev = $step;
$step += floor(sqrt($length));
if ($prev >= $length) return -1;
}
for ($i = $prev; $i < min($step, $length); $i++) {
if ($arr[$i] == $target) return $i;
}
return -1;
}
$array = [2, 4, 6, 8, 10, 12];
$target = 8;
$index = jumpSearch($array, $target);
if ($index != -1) echo "Element $target found at index $index using function.";
else echo "Element $target not found using function.";
?>By using a function, beginners can easily search multiple arrays without rewriting the search logic. This approach also reinforces modular programming and code reusability.
Program 3: Jump Search Using Recursion
Although less common, Jump Search can be implemented recursively. This program demonstrates a recursive approach for searching a target value.
<?php
function recursiveJumpSearch($arr, $target, $start = 0, $step = null) {
$length = count($arr);
if ($step === null) $step = floor(sqrt($length));
if ($start >= $length) return -1;
$end = min($start + $step - 1, $length - 1);
if ($arr[$end] >= $target) {
for ($i = $start; $i <= $end; $i++) {
if ($arr[$i] == $target) return $i;
}
return -1;
}
return recursiveJumpSearch($arr, $target, $start + $step, $step);
}
$array = [1, 3, 5, 7, 9, 11, 13];
$target = 11;
$index = recursiveJumpSearch($array, $target);
if ($index != -1) echo "Element $target found at index $index using recursion.";
else echo "Element $target not found using recursion.";
?>This recursive approach helps beginners understand how the search space can be divided into blocks and explored step by step. It also reinforces concepts like base cases and recursion, which are important in programming.
Program 4: Jump Search for Strings
Jump Search can also be applied to sorted arrays of strings. This program demonstrates searching for a name in an alphabetical list.
<?php
$names = ["Albus", "Fred", "George", "Hermione", "Ron"];
$target = "Hermione";
$length = count($names);
$step = floor(sqrt($length));
$prev = 0;
while (strcmp($names[min($step, $length) - 1], $target) < 0) {
$prev = $step;
$step += floor(sqrt($length));
if ($prev >= $length) {
echo "Name $target not found.";
exit;
}
}
for ($i = $prev; $i < min($step, $length); $i++) {
if ($names[$i] === $target) {
echo "Name $target found at index $i.";
exit;
}
}
echo "Name $target not found.";
?>By using strcmp for comparison, beginners learn that Jump Search is flexible and can handle text as well as numbers. This is useful for searching names, words, or other textual data in sorted arrays.
Program 5: Jump Search with Multiple Occurrences
This program demonstrates how to find all occurrences of a target value in a sorted array using Jump Search.
<?php
$array = [2, 4, 4, 4, 6, 8, 10];
$target = 4;
$indices = [];
$length = count($array);
$step = (int)floor(sqrt($length));
$prev = 0;
// find the block where target may be
while ($prev < $length && $array[min($step, $length) - 1] < $target) {
$prev = $step;
$step += (int)floor(sqrt($length));
if ($prev >= $length) {
echo "Element $target not found.";
exit;
}
}
// find any one index of target inside that block
$foundIndex = -1;
for ($i = $prev; $i < min($step, $length); $i++) {
if ($array[$i] === $target) {
$foundIndex = $i;
break;
}
}
if ($foundIndex === -1) {
echo "Element $target not found.";
exit;
}
// expand left and right from the found index to collect all duplicates
$l = $foundIndex;
while ($l - 1 >= 0 && $array[$l - 1] === $target) $l--;
$r = $foundIndex;
while ($r + 1 < $length && $array[$r + 1] === $target) $r++;
// gather indices
for ($i = $l; $i <= $r; $i++) $indices[] = $i;
echo "Element $target found at indices: " . implode(", ", $indices) . ".";
?>This example shows how to adapt Jump Search for practical scenarios where duplicates exist. Beginners learn how to extend the algorithm to handle multiple occurrences while still benefiting from step-wise searching.
Frequently Asked Questions (FAQ)
Jump Search is an efficient search algorithm, but beginners often have questions about how and when to use it.
Q1: When should I use Jump Search?
Jump Search works best for sorted arrays where skipping blocks reduces comparisons.
Q2: Is Jump Search faster than Linear Search?
Yes, it reduces the number of checks by jumping ahead, making it faster for large sorted arrays.
Q3: Can Jump Search work with strings?
Yes, with alphabetical sorting and using string comparison functions like strcmp.
Q4: What is the time complexity of Jump Search?
The time complexity is O(√n), making it more efficient than linear search for large datasets.
Q5: Can Jump Search handle multiple occurrences?
Yes, by scanning the identified block, all duplicates can be found efficiently.
Conclusion
Jump Search is a practical and beginner-friendly algorithm for searching sorted arrays efficiently. By practicing loops, recursion, handling strings, and managing multiple occurrences, learners can understand how step-wise searching reduces comparisons and improves performance. These PHP examples make Jump Search approachable and show how it can be applied to numbers, names, and real-world data. Practicing this algorithm will strengthen your understanding of array traversal and efficient search techniques, preparing you for more advanced programming challenges.
