Jump Search

February 17, 2019 3 minutes

Just like Binary Search, Jump Search is also applicable only on sorted elements and works by dividing the entire dataset into smaller partitions. This technique helps these algorithms to reduce the overall time complexity to search for an element.

The basic idea in Jump Search is to consider only a subset of the entire dataset at any given point of time and to see if the key element (the element that we need to find) is present in it or not. If the element is present the subset/partition, we perform a sequential search on this partition or else we move to the next partition.

This way, we reduce the number of comparisons done as compared to the sequential searching algorithm, Linear Search by skipping some of the partitions.

Example:

Let’s try to understand the algorithm with the help of an example. Consider a sorted input dataset of the following members {1,2,3,4,5,6,7,8,9,10}. Let’s say we need to find the element: 9

We logically divide the dataset into sub-sets of size 3 (called m) i.e. we consider only 3 elements in every iteration. How we decide the size of the subsets, is explained later in this post. So the dataset can be imagined to look something like: {{1,2,3}, {4,5,6}, {7,8,9}, {10}}

Next we start comparing elements at index 0, 0+m, 0+2m and so-on until we find a number which is greater than the key element. Once we find such a set, we can conclude that the key element will lie in the subset before it and we can then perform a linear search (generally starting from the last element) on that set to find the element.

So this way, we do the following comparisons:

JumpSearch

Block size

Let’s say we divided the input of size n to m sized blocks. The worst-case scenario will happen when we must do maximum number of jumps and then a linear search on the identified block.

This will happen when the value to be found is in the second last block. So in that case:

  • We’ll take the maximum number of jumps (i.e. $\frac {n}{m}$)
  • And will then perform a linear search on the block of size m as well.

The overall number of calculations performed in such a scenario will be : $\frac{n}{m}+(m−1)$ now this equation will be minimum for $m = \sqrt{n}$. Hence the block size is selected as the same.

Java Implementation

The above mentioned algorithm can be implemeted in java as follows :

    public int search(int[] input, int key) {
        int size = input.length;         
	int pivot = (int) Math.sqrt(size);

        //in every iteration, increment by the numeric value of pivot 
	for (int forwardIndex = 0; forwardIndex < size; forwardIndex += pivot) {
            if (input[forwardIndex] == key) {                 
		return forwardIndex;             
	    } 
	    else if (input[forwardIndex] > key) {
                int end = forwardIndex - pivot;

		//now iterate backwards
                for (int backwardIndex = forwardIndex - 1; backwardIndex >= end; backwardIndex--) {
                    if (input[backwardIndex] == key) {
                        return backwardIndex;
                    }
                }
            }
        }
        return -1;
    }

A working example with test cases can be found here


comments powered by Disqus