Searching Algorithm 3: Jump search

In this chapter we shall learn about below topics:

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.

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.

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:

#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;
}

Time complexity is O(√n).