**What is Jump Search Algorithm?**

Like Binary Search, Jump Search is a scanning calculation for arranged clusters. The fundamental thought is to check fewer components (than direct hunt) by hopping ahead by fixed advances or skirting a few components instead of looking through all components.

For instance, assume we have an array arr[] of size n and square (to be hopped) size m. At that point we search at the records arr[0], arr[m], arr[2m]… ..arr[km], etc. When we discover the stretch (arr[km] < x < arr[(k+1)m]), we play out a straight pursuit activity from the file km to discover the component x.

How about we think about the accompanying array: (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610). Length of the cluster is 16. Bounce search will discover the estimation of 55 with the accompanying advances expecting that the square size to be hopped is 4.

- Stage 1: Go from index 0 to index 4
- Stage 2: Go from index 4 to index 8
- Stage 3: Go from index 8 to index 12
- Stage 4: Since the component at a record 12 is more prominent than 55 we will bounce back a stage to come to list 8
- Stage 5: Perform straight pursuit from list 8 to get the component 55.

**What is the ideal square size to be skipped?**

**What is the ideal square size to be skipped?**

In the most pessimistic scenario, we need to do n/m hops and if the last checked worth is more prominent than the component to be looked for, we perform m-1 correlations more for straight hunt. In this way the absolute number of examinations in the most pessimistic scenario will be ((n/m) + m-1). The estimation of the capacity ((n/m) + m-1) will be least when m = √n. In this manner, the best advance size is m = √n.

##
**Implementation of Jump Search Algorithm**:

In this program we have implemented the Jump search algorithm in C++ language:

#include<iostream>

#include<cmath>

using namespace std;

int jumpSearch(int a[], int n, int item) {

int i = 0;

int m = sqrt(n); //initialise the 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 = jumpSearch(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 we have used in the **example**:

**Note:** The calculation can be actualised in any programming language according to the necessity.

Must Read, __binary search algorithm__