Dark Mode On/Off

Jump Search Algorithm is a relatively new algorithm for searching an element in a sorted array.

The fundamental idea behind this searching technique is to search fewer number of elements compared to linear search algorithm (which scans every element in the array to check if it matches with the element being searched or not). This can be done by skipping some fixed number of array elements or **jumping ahead by fixed number of steps** in every iteration.

Lets consider a sorted array `A[]`

of size `n`

, with indexing ranging between **0** and **n-1**, and element **x** that needs to be searched in the array `A[]`

. For implementing this algorithm, a block of size **m** is also required, that can be skipped or jumped in every iteration. Thus, the algorithm works as follows:

**Iteration 1**: if (`x==A[0]`

), then success, else, if (`x > A[0]`

), then jump to the next block.**Iteration 2**: if (`x==A[m]`

), then success, else, if (`x > A[m]`

), then jump to the next block.**Iteration 3**: if (`x==A[2m]`

), then success, else, if (`x > A[2m]`

), then jump to the next block.- At any point in time, if (
`x < A[km]`

), then a**linear search**is performed from index`A[(k-1)m]`

to`A[km]`

Figure 1: Jump Search technique

`m`

(Block size to be skipped)The worst-case scenario requires:

`n/m`

jumps, and`(m-1)`

comparisons (in case of linear search if`x < A[km]`

)

Hence, the total number of comparisons will be `(n/m+(m-1))`

. This expression has to be minimum, so that we get the smallest value of m (block size).

On differentiating this expression with respect to `m`

and equating it with **0**, we get:

`n/-m`^{2}+1 = 0
n/m^{2} = 1
m = √n

Hence, the **optimal jump size** is **√n**, where **n** is the size of the array to be searched or the total number of elements to be searched.

Below we have the algorithm for implementing Jump search:

**Input** will be:

- Sorted array
`A`

of size`n`

- Element to be searched, say
`item`

**Output** will be:

- A valid location of
`item`

in the array`A`

**Steps for Jump Search Algorithms:**

**Step 1**: Set `i=0`

and `m = √n`

.

**Step 2**: Compare `A[i]`

with `item`

. If `A[i] != item`

and `A[i] < item`

, then jump to the next block. Also, do the following:

- Set
**i = m** - Increment
`m`

by`√n`

**Step 3**: Repeat the step 2 till **m < n-1**

**Step 4**: If `A[i] > item`

, then move to the beginning of the current block and perform a linear search.

- Set
**x = i** - Compare
`A[x]`

with`item`

. If`A[x]== item`

, then print`x`

as the valid location else set`x++`

- Repeat Step 4.1 and 4.2 till
**x < m**

**Step 5**: Exit

Let us trace the above algorithm using an example:

Consider the following inputs:

`A[]`

= {0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 77, 89, 101, 201, 256, 780}`item`

= 77

**Step 1**: **m = √n = 4** (Block Size)

**Step 2**: Compare `A[0]`

with `item`

. Since **A[0] != item** and **A[0]<item**, skip to the next block

Figure 2: Comparing A[0] and item

**Step 3**: Compare A[3] with item. Since A[3] != itemand A[3]<item, skip to the next block

Figure 3: Comparing A[3] and item

**Step 4**: Compare A[6] with item. Since A[6] != itemand A[6]<item, skip to the next block

Figure 4: Comparing A[6] and item

**Step 5**: Compare A[9] with item. Since A[9] != itemand A[9]<item, skip to the next block

Figure 5: Comparing A[9] and item

**Step 6**: Compare A[12] with item. Since A[12] != item and A[12] >item, skip to A[9] (beginning of the current block) and perform a linear search.

Figure 6: Comparing A[12] and item

Figure 7: Comparing A[9] and item (Linear Search)

- Compare A[9] with item. Since A[9] != item, scan the next element
- Compare A[10] with item. Since A[10] == item, index 10 is printed as the valid location and the algorithm will terminate

Figure 8: Comparing A[10] and item (Linear Search)

Following is the program in which we have implemented the Jump search algorithm in C++ language:

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

The input array is the same as that used in the example:

**Note:** The algorithm can be implemented in any programming language as per the requirement.

Let's see what will be the time and space complexity for the Jump search algorithm:

The while loop in the above C++ code executes n/m times because the loop counter increments by m times in every iteration. Since the optimal value of m= √n , thus, n/m=√n resulting in a time complexity of **O(√n)**.

The space complexity of this algorithm is **O(1)** since it does not requireany other data structure for its implementation.

- This algorithm works only for sorted input arrays
- Optimal size of the block to be skipped is √n, thus resulting in the time complexity O(√n
^{2}) - The time complexity of this algorithm lies in between linear search (O(n)) and binary search (O(log n))
- It is also called block search algorithm

- It is faster than the linear search technique which has a time complexity of O(n) for searching an element

- It is slower than binary search algorithm which searches an element in O(log n)
- It requires the input array to be sorted