Jump search algorithm is a pretty new algorithm to search for an element in a sorted array.

The idea of jump search is to skip the number of comparisons by jumping the indices by length **m** while performing the searching thus getting a better time complexity than linear search.

For jump search **m** is determined by the square root of the length of the array **m= √n**

Let’s take the below sorted array **A[]**, the target to find is 16, in a linear search algorithm it would take O(n) time complexity to find the number 16, in jump search we would jump the indices of size **m= √n** from 0->4->8->12->16 and would be able to find in O(√n)

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |

**Algorithm:**

- Find jump block size
**m=√n**. - If
**A[i] == target**return i (i= index to compare). - If
**A[i] < target**i= m and increment**m + √n**. - Repeat the above step till
**m<n-1**. - If
**A[i] >target**perform linear search from A[i-**√n**] to A[i].

Heres the video explanation

Now we have seen the algorithm let’s see how the code looks

```
public static int jumpSearch(int[] a, int target) {
int m = (int) Math.floor(Math.sqrt(a.length));
int currentLastIndex = m-1;
// Jump to next block as long as target element is > currentLastIndex
while (currentLastIndex < a.length && target > a[currentLastIndex]) {
currentLastIndex += m;
}
// Find the accurate position of target number using Linear Search
for (int currentSearchIndex = currentLastIndex - m + 1;
currentSearchIndex <= currentLastIndex && currentSearchIndex < a.length; currentSearchIndex++) {
if (target == a[currentSearchIndex]) {
return currentSearchIndex;
}
}
// If target number not found, return negative integer as element position.
return -1;
}
```