Jump search Algorithm explained

Search algorithms are used in programming when programmers have to search for an element in an array. While there are many search algorithm exists, Jump search is one of the popular search algorithms that is quick, easy to implement in any programming language. This article explains the usage of Jump search algorithm in detail with a sample code.

Jump search Algorithm:

The most important thing about Jump search is that it works only on sorted arrays. There are number of sorting algorithms such as Insertion sort, Selection sort, Bubble sort, etc that we can use to sort the elements in an array. The number of blocks searched to find the target element in the jump search is very less as compared to linear search. The jumping of the search can be controlled based on the number of the elements that can be skipped in one jump. This reduces the time to search the element and provides the efficient search time.

Explanation of Jump search algorithm:

Let us consider the sorted array and search for an element in the array by considering the particular block size and execute the Jump search algorithm.

Let us consider the searching for number 10 in the above array using jump search. As you can see the above array is sorted and it meets our requirement to use Jump search algorithm. Since this is a small array let’s consider a searching block size of 2.

Now, the search starts from the beginning and searches for the target element. Initially, the initial block is considered with the first element say i=2 and last element j=5. Since the target number is not in the range of the first block, the search jumps to the next block.

Circuits Library - 220+ practical circuits

The search range moves to the second block with i=7 and j=8, since the target element does not lie in this range, the search jumps to the next block.

Now, the search moves to the next block with i=10 and j=12. The target element is found in the first element i=10.

In this way Jump search algorithm can be used to search for elements in an array. Increasing the search block size will improve the speed when searching for values in an array of bigger size.

Implementation of Jump Search algorithm:

Considering the above example, the jump search can be implemented based on the algorithm.
Consider the block size, m=2
First element is i and second element is j
Target element can be stored in variable t
Now, initially from first element the search starts, and searches the target element till the end
Finally, the target element can be found if present in the sorted array.

Sample code:

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

Code source: Studytonight