Jump Search

Jump search algorithm, also called as block search algorithm. Only sorted list of array or table can alone use the Jump search algorithm. In jump search algorithm, it is not at all necessary to scan every element in the list as we do in linear search algorithm. We just check the R element and if it is less than the key element, then we move to the R + R element, where all the elements between R element and R + R element are skipped. This process is continued until R element becomes equal to or greater than key element called boundary value. The value of R is given by R = sqrt(n), where n is the total number of elements in an array. Once the R element attain the boundary value, a linear search is done to find the key value and its position in the array. It must be noted that in Jump search algorithm, a linear search is done in reverse manner that is from boundary value to previous value of R.

Example - Jump Search

In 16 elements of array, we need to find our key element 7 using jump search algorithm.

step 1: Find the value of R. here R = sqrt (16) i.e) R = 4.

step 2: Skip the first three elements(1, 2, 3) in the array and check whether fourth(4) value is equal to or greater than key value(7).

step 3: If not skip next three elements(5, 6, 7) in the array and check whether eighth(8) value is equal to or greater than key value(7). In this case it is greater than Key value.

step 4: Now by using linear search algorithm, move reverse from value 8(boundary value) to value 4(previous value) to find the key value(7).

step 5: Thus using linear search algorithm the Key value is calculated and resulted in position array[6].

Advantages - Jump Search

• Jump search algorithm is more efficient in case of finding a element 600 out of 625 elements in an array.
• Jump search algorithm takes 25 iteration to find a element 600 out of 625 elements in an array.
• Whereas Linear search algorithm takes 600 iteration to find a element 600 out of 625 elements in an array.
• Whereas Binary search algorithm takes 19 iteration to find a element 600 out of 625 elements in an array but complexity in calculation is very tough as compared to jump search algorithm.

Disadvantages - Jump Search

• Jump search algorithm is not preferable for unsorted list or array.
• Executing time of Binary search algorithm is 0 (sqrt (n)).

C program - Jump Search

Here is the program to demonstrate Jump Search.

#include <stdio.h>
#include <math.h>
#define MAXVALUE 30
int jump_search(int a[], int low, int high, int val, int n)
{
int step, i;
step = n;
for(i=0; i<step; i++)
{
if(val < a[step])
high = step - 1;
else
low = step + 1;
}
for(i=low; i<=high; i++)
{
if(a[i] == val)
return i;
}
return -1;
}
int main()
{
int arry[MAXVALUE], i, n, val, pos;
printf("\n Enter the size of the array : ");
scanf("%d", &n);
printf("\n Enter %d elements in the array : \n",n);
for(i=0; i<n; i++)
scanf("%d",&arry[i]);
printf("\n Enter the key element that has to be search : ");
scanf("%d", &val);
pos = jump_search(arry, 0, n-1,val, n);
if(pos == -1)
printf("\n %d is not found in the array ", val);
else
printf("\n %d is found at position arry [%d]", val,pos);
return 0;
}

Enter the size of the array : 5 
Enter 5 elements in the array :
1 2 3 4 5 
Enter the key element that has to be search : 3
3 is found in the array at position arry [2]

Report Us

We may make mistakes(spelling, program bug, typing mistake and etc.), So we have this container to collect mistakes. We highly respect your findings.

Report

Error Line Corrected Line Send