What is jump search?

Jump search algorithm is a pretty new algorithm to search for an element in a sorted array. Jump search, also called as block search algorithm. Only sorted list of array or table can alone use the Jump search algorithm. In jump search algorithm, it is not at all necessary to scan every element in the list as we do in linear search algorithm. We just check the R element and if it is less than the key element, then we move to the R + R element, where all the elements between R element and R + R element are skipped. This process is continued until R element becomes equal to or greater than key element called boundary value. The value of R is given by R = sqrt(n), where n is the total number of elements in an array. Once the R element attain the boundary value, a linear search is done to find the key value and its position in the array. It must be noted that in Jump search algorithm, a linear search is done in reverse manner that is from boundary value to previous value of R.

Algorithm:

Find jump block size m=√n.

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

Important points:

• Works only sorted arrays.
• The optimal size of a block to be jumped is (√ n).
• Binary Search is better than Jump Search, but Jump search has an advantage that we traverse back only once (Binary Search may require up to O(Log n) jumps, consider a situation where the element to be search is the smallest element or smaller than the smallest). So in a systems where jumping back is costly, we use Jump Search.

Complexity

The time complexity of Jump Search is between Linear Search ((O(n)) and Binary Search (O(Log n)).

The Jump search algorithm takes O(√n) time complexity.

Since we are not creating any other temporary data structure, the jump search algorithm takes O(1) space complexity.

Java example

Java program to implement Jump Search

public class JumpSearch {

public static int jumpSearch(int[] arr, int x) { 

    int n = arr.length;
    int step = (int)Math.floor(Math.sqrt(n)); 
    int prev = 0; 
    while (arr[Math.min(step, n)-1] < x) { 
        prev = step; 
        step += (int)Math.floor(Math.sqrt(n)); 
        if (prev >= n) 
            return -1; 
    } 

    while (arr[prev] < x) {

        prev++; 

        if (prev == Math.min(step, n)) 
            return -1; 
    } 

    if (arr[prev] == x) 
        return prev; 

    return -1; 
} 

public static void main(String [ ] args) { 
    int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 
                34, 55, 89, 144, 233, 377, 610}; 
    int x = 55; 

    int index = jumpSearch(arr, x); 

    System.out.println(" Number " + x + " is at index " + index); 
} 

}

How the algorithm works