WikiGalaxy
Jump Search Algorithm
Introduction to Jump Search
Jump Search is an algorithm used to search for an element in a sorted array. It works by dividing the array into blocks of a fixed size and performing a linear search within the block where the element is likely to be found. This method reduces the number of comparisons compared to linear search, making it more efficient for larger datasets.
How Jump Search Works
The Jump Search algorithm follows these steps:
- Determine the block size to jump. This is typically the square root of the array's length.
- Jump ahead by the block size until the end of the array or until the element at the current block exceeds the target element.
- Perform a linear search within the block where the target element may exist.
Example 1: Basic Jump Search
Array: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Search for the element 7 using Jump Search.
int jumpSearch(int[] arr, int x) {
int n = arr.length;
int step = (int)Math.floor(Math.sqrt(n));
int prev = 0;
while (arr[Math.min(step, n)-1] < x) {
prev = step;
step += (int)Math.floor(Math.sqrt(n));
if (prev >= n)
return -1;
}
while (arr[prev] < x) {
prev++;
if (prev == Math.min(step, n))
return -1;
}
if (arr[prev] == x)
return prev;
return -1;
}
Explanation:
The array is divided into blocks of size 3 (since the square root of 10 is approximately 3). The search jumps through the blocks until it finds the range containing the number 7, then performs a linear search within that block.
Example 2: Jump Search with Larger Array
Array: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]
Search for the element 19 using Jump Search.
int jumpSearch(int[] arr, int x) {
int n = arr.length;
int step = (int)Math.floor(Math.sqrt(n));
int prev = 0;
while (arr[Math.min(step, n)-1] < x) {
prev = step;
step += (int)Math.floor(Math.sqrt(n));
if (prev >= n)
return -1;
}
while (arr[prev] < x) {
prev++;
if (prev == Math.min(step, n))
return -1;
}
if (arr[prev] == x)
return prev;
return -1;
}
Example 3: Jump Search with Non-Existent Element
Array: [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
Search for the element 5 using Jump Search.
int jumpSearch(int[] arr, int x) {
int n = arr.length;
int step = (int)Math.floor(Math.sqrt(n));
int prev = 0;
while (arr[Math.min(step, n)-1] < x) {
prev = step;
step += (int)Math.floor(Math.sqrt(n));
if (prev >= n)
return -1;
}
while (arr[prev] < x) {
prev++;
if (prev == Math.min(step, n))
return -1;
}
if (arr[prev] == x)
return prev;
return -1;
}
Explanation:
Despite jumping through the blocks, the element 5 is not found in the array, resulting in a return value of -1, indicating the element is not present.
Example 4: Jump Search with Small Array
Array: [4, 8, 12, 16]
Search for the element 12 using Jump Search.
int jumpSearch(int[] arr, int x) {
int n = arr.length;
int step = (int)Math.floor(Math.sqrt(n));
int prev = 0;
while (arr[Math.min(step, n)-1] < x) {
prev = step;
step += (int)Math.floor(Math.sqrt(n));
if (prev >= n)
return -1;
}
while (arr[prev] < x) {
prev++;
if (prev == Math.min(step, n))
return -1;
}
if (arr[prev] == x)
return prev;
return -1;
}
Explanation:
With a small array, the block size is effectively 2. The search quickly identifies the block containing 12 and locates it through a linear search.
Example 5: Jump Search in a Large Array
Array: [1, 2, 3, ..., 100]
Search for the element 75 using Jump Search.
int jumpSearch(int[] arr, int x) {
int n = arr.length;
int step = (int)Math.floor(Math.sqrt(n));
int prev = 0;
while (arr[Math.min(step, n)-1] < x) {
prev = step;
step += (int)Math.floor(Math.sqrt(n));
if (prev >= n)
return -1;
}
while (arr[prev] < x) {
prev++;
if (prev == Math.min(step, n))
return -1;
}
if (arr[prev] == x)
return prev;
return -1;
}
Explanation:
In a larger array, the block size is 10. The search efficiently narrows down the range to locate the element 75, reducing the number of comparisons significantly compared to a linear search.
