HackerHeap

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