# Jump Search Algorithm In Java 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)

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