Jump Search
In this page:
What is Jump Search
Jump search works on sorted data by skipping ahead in fixed-size blocks rather than checking every element, jumping forward until it finds a block that might contain the target, then searching within just that block.
Example: What is Jump Search
#include <iostream>
using namespace std;
int main() {
int arr[] = {1,3,5,7,9,11,13,15,17,19}, n = 10, target = 13, step = 3, i = 0;
while (i < n && arr[i] < target) i += step;
cout << "Jumped to block starting at index " << i << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {1,3,5,7,9,11,13,15,17,19};
int target = 13, step = 3, i = 0;
while (i < arr.length && arr[i] < target) i += step;
System.out.println("Jumped to block starting at index " + i);
}
}arr = [1,3,5,7,9,11,13,15,17,19]
target, step, i = 13, 3, 0
while i < len(arr) and arr[i] < target:
i += step
print("Jumped to block starting at index", i)#include <stdio.h>
int main() {
int arr[] = {1,3,5,7,9,11,13,15,17,19}, n = 10, target = 13, step = 3, i = 0;
while (i < n && arr[i] < target) i += step;
printf("Jumped to block starting at index %d\n", i);
return 0;
}Login to try C/C++/Java code in the editor
Jump Size
The typical block size is the square root of the array's length — this specific size balances the number of jumps against the size of the final linear scan, minimizing the total work in the worst case.
Example: Jump Size
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int n = 100;
int blockSize = (int)sqrt(n);
cout << "Optimal block size for n=" << n << " is " << blockSize << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int n = 100;
int blockSize = (int) Math.sqrt(n);
System.out.println("Optimal block size for n=" + n + " is " + blockSize);
}
}import math
n = 100
block_size = int(math.sqrt(n))
print("Optimal block size for n=", n, "is", block_size)#include <stdio.h>
#include <math.h>
int main() {
int n = 100;
int blockSize = (int)sqrt((double)n);
printf("Optimal block size for n=%d is %d\n", n, blockSize);
return 0;
}Login to try C/C++/Java code in the editor
Linear Scan
Once a block is found where the target could plausibly be (the block's last element is greater than or equal to the target), jump search falls back to a simple linear scan within just that block to pinpoint the exact position.
Example: Linear Scan
#include <iostream>
using namespace std;
int main() {
int arr[] = {1,3,5,7,9,11,13}, target = 7, step = 3;
int prev = 0, i = 0;
while (i < 7 && arr[i] < target) { prev = i; i += step; }
for (int j = prev; j < 7 && arr[j] <= target; j++)
if (arr[j] == target) { cout << "Found at index " << j << endl; break; }
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {1,3,5,7,9,11,13};
int target = 7, step = 3, prev = 0, i = 0;
while (i < arr.length && arr[i] < target) { prev = i; i += step; }
for (int j = prev; j < arr.length; j++)
if (arr[j] == target) { System.out.println("Found at index " + j); break; }
}
}arr = [1,3,5,7,9,11,13]
target, step, prev, i = 7, 3, 0, 0
while i < len(arr) and arr[i] < target:
prev = i
i += step
for j in range(prev, len(arr)):
if arr[j] == target:
print("Found at index", j)
break#include <stdio.h>
int main() {
int arr[] = {1,3,5,7,9,11,13}, target = 7, step = 3, prev = 0, i = 0;
while (i < 7 && arr[i] < target) { prev = i; i += step; }
for (int j = prev; j < 7; j++)
if (arr[j] == target) { printf("Found at index %d\n", j); break; }
return 0;
}Login to try C/C++/Java code in the editor
Complexity
Jump search takes about O(√n) comparisons in the worst case — slower than binary search's O(log n) but faster than plain linear search's O(n), sitting as a middle ground between the two approaches.
Example: Complexity
#include <iostream>
using namespace std;
int main() {
cout << "Jump search: about O(sqrt n) comparisons -- slower than O(log n) binary search, faster than O(n) linear search" << endl;
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Jump search: about O(sqrt n) comparisons -- slower than O(log n) binary search, faster than O(n) linear search");
}
}print("Jump search: about O(sqrt n) comparisons -- slower than O(log n) binary search, faster than O(n) linear search")#include <stdio.h>
int main() {
printf("Jump search: about O(sqrt n) comparisons -- slower than O(log n) binary search, faster than O(n) linear search\n");
return 0;
}Login to try C/C++/Java code in the editor
Requirements and Uses
Jump search requires sorted data, same as binary search, and is mainly useful when jumping backward is expensive (such as on certain storage media where sequential forward access is much cheaper than random access) — in ordinary in-memory arrays, binary search is usually the better default.
Example: Requirements and Uses
#include <iostream>
using namespace std;
int main() {
cout << "Jump search requires sorted data; useful when backward seeks are expensive (e.g. tape storage)" << endl;
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Jump search requires sorted data; useful when backward seeks are expensive (e.g. tape storage)");
}
}print("Jump search requires sorted data; useful when backward seeks are expensive (e.g. tape storage)")#include <stdio.h>
int main() {
printf("Jump search requires sorted data; useful when backward seeks are expensive (e.g. tape storage)\n");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 5 topics to unlock
0/5 topics done
Complete these topics first: