Jump Search Algorithm is a relatively new algorithm for searching an element in a sorted array.
The fundamental idea behind this searching technique is to search fewer number of elements compared to linear search algorithm (which scans every element in the array to check if it matches with the element being searched or not). This can be done by skipping some fixed number of array elements or jumping ahead by fixed number of steps in every iteration.
Lets consider a sorted array A[]
of size n
, with indexing ranging between 0 and n-1, and element x that needs to be searched in the array A[]
. For implementing this algorithm, a block of size m is also required, that can be skipped or jumped in every iteration. Thus, the algorithm works as follows:
x==A[0]
), then success, else, if (x > A[0]
), then jump to the next block.x==A[m]
), then success, else, if (x > A[m]
), then jump to the next block.x==A[2m]
), then success, else, if (x > A[2m]
), then jump to the next block.x < A[km]
), then a linear search is performed from index A[(k-1)m]
to A[km]
Figure 1: Jump Search technique
m
(Block size to be skipped)The worst-case scenario requires:
n/m
jumps, and(m-1)
comparisons (in case of linear search if x < A[km]
)Hence, the total number of comparisons will be (n/m+(m-1))
. This expression has to be minimum, so that we get the smallest value of m (block size).
On differentiating this expression with respect to m
and equating it with 0, we get:
n/-m2+1 = 0
n/m2 = 1
m = √n
Hence, the optimal jump size is √n, where n is the size of the array to be searched or the total number of elements to be searched.
Below we have the algorithm for implementing Jump search:
Input will be:
A
of size n
item
Output will be:
item
in the array A
Steps for Jump Search Algorithms:
Step 1: Set i=0
and m = √n
.
Step 2: Compare A[i]
with item
. If A[i] != item
and A[i] < item
, then jump to the next block. Also, do the following:
m
by √n
Step 3: Repeat the step 2 till m < n-1
Step 4: If A[i] > item
, then move to the beginning of the current block and perform a linear search.
A[x]
with item
. If A[x]== item
, then print x
as the valid location else set x++
Step 5: Exit
Let us trace the above algorithm using an example:
Consider the following inputs:
A[]
= {0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 77, 89, 101, 201, 256, 780}item
= 77Step 1: m = √n = 4 (Block Size)
Step 2: Compare A[0]
with item
. Since A[0] != item and A[0]<item, skip to the next block
Figure 2: Comparing A[0] and item
Step 3: Compare A[3] with item. Since A[3] != itemand A[3]<item, skip to the next block
Figure 3: Comparing A[3] and item
Step 4: Compare A[6] with item. Since A[6] != itemand A[6]<item, skip to the next block
Figure 4: Comparing A[6] and item
Step 5: Compare A[9] with item. Since A[9] != itemand A[9]<item, skip to the next block
Figure 5: Comparing A[9] and item
Step 6: Compare A[12] with item. Since A[12] != item and A[12] >item, skip to A[9] (beginning of the current block) and perform a linear search.
Figure 6: Comparing A[12] and item
Figure 7: Comparing A[9] and item (Linear Search)
Figure 8: Comparing A[10] and item (Linear Search)
Following is the program in which we have implemented the Jump search algorithm in C++ language:
#include<iostream>
#include<cmath>
using namespace std;
int jump_Search(int a[], int n, int item) {
int i = 0;
int m = sqrt(n); //initializing block size= √(n)
while(a[m] <= item && m < n) {
// the control will continue to jump the blocks
i = m; // shift the block
m += sqrt(n);
if(m > n - 1) // if m exceeds the array size
return -1;
}
for(int x = i; x<m; x++) { //linear search in current block
if(a[x] == item)
return x; //position of element being searched
}
return -1;
}
int main() {
int n, item, loc;
cout << "\n Enter number of items: ";
cin >> n;
int arr[n]; //creating an array of size n
cout << "\n Enter items: ";
for(int i = 0; i< n; i++) {
cin >> arr[i];
}
cout << "\n Enter search key to be found in the array: ";
cin >> item;
loc = jump_Search(arr, n, item);
if(loc>=0)
cout << "\n Item found at location: " << loc;
else
cout << "\n Item is not found in the list.";
}
The input array is the same as that used in the example:
Note: The algorithm can be implemented in any programming language as per the requirement.
Let's see what will be the time and space complexity for the Jump search algorithm:
The while loop in the above C++ code executes n/m times because the loop counter increments by m times in every iteration. Since the optimal value of m= √n , thus, n/m=√n resulting in a time complexity of O(√n).
The space complexity of this algorithm is O(1) since it does not requireany other data structure for its implementation.