Jump search is an improvement over linear search. In linear search, we check the element one by one till we find the key element, or till we reach the end of the array.
But what if we can find the key element way faster than linear search?
The answer to that is jump search. Jump search will work if the array is sorted.
In jump search we jump block by block and check if the key element is inside the block. If the key element is inside the block, we do a linear search in that block.
How to choose the block or Jump size?
If the jump size is 1, then it will be a linear search. Hence we usually take the jump size of SQRT(n). By doing so, in the worst case we do n/k jumps.
Now let us understand the algorithm with help of example:
1, 1, 2, 3, 4, 10, 15, 20, 75, 80, 92, 95, 100
Key = 80
N = 13
Jump = SQRT(13) = 3
Below image show the passes:
Jump search in C++
#include<iostream>
#include <cmath>
#include <vector>
using namespace std;
void jump_search(int arr[], int key, int len)
{
int jump = sqrt(len);
int start = 0;
int end = start + jump;
// get the correct block to search
while (end < len && arr[end] <= key)
{
// update the variables to make the jump.
start = end;
end += jump;
// check if the end is greater than the size,
//if yes, reset it.
if(end > len - 1)
end = len;
}
// now do a linear search in the block
for(int i = start; i<end; i++)
{
if(arr[i] == key)
cout<<" The key is present in the array"<<endl;
return;
}
cout<<" The key is NOT in the array"<<endl;
}
int main()
{
int arr[20] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
int key = 13;
int len = 15;
jump_search(arr, key, len);
return 0;
}
Further Reading:
