Jump Search in Java

Introduction

Be it searching through a play-list for your favorite song or searching through a catalog to pick the restaurant to have your next meal in, our lives are filled with searching for things.

In quite the same way, computers perform search queries on their data collections and structures. However, in contrast to humans, computers have to carry out searches on much larger datasets in times that are orders of magnitude faster than humans.

This drove Computer Scientists to come up with many search algorithms, where each is typically more optimal than some other on certain collections.

Jump Search

Jump Search (also referred to as Block Search) is an algorithm used to search for the position of a target element on a sorted data collection or structure.

Instead of searching the array element-by-element (Linear Search) - Jump Search evaluates blocks of elements. Or rather, since it's a sorted array - the element with the highest value in each block.

If the value is smaller than the target element, the next block is considered.
If the value is higher than the target element, the target element is in the current block.
If the value is the target element - just return it.

By iteratively shifting, or rather jumping forward, we'll either find the target element or reach the end of the collection without finding it.

Here’s a visual representation of how Jump Search works:

Evidently, Jump Search always seeks forward on its arrays unlike back and forth search methods like Binary Search. This behavior makes Jump Search much more efficient for searches on data stored on physical drives with spinning mediums.

Furthermore, another way to understand this search is without blocks - there's simply a Jump Gap between the evaluated elements. No real block is being saved in the memory as the algorithm executes.

Implementation

That being said, let's implement Jump Search. There are two approaches that you can take, without a real "winner" between these two - the iterative and recursive implementation.

Choosing between these two is up to you and unless you're working on insanely huge datasets, there shouldn't be a difference in performance. Recursion leads to higher processor/memory space usage but is typically cleaner to read and write.

Then again, if you're working on really big datasets, you'd probably use more efficient, optimized search algorithms.

Iterative Implementation

That being said, let's start off with the iterative approach:

public static int jumpSearch(int[] arrayToSearch, int element) {
    int blockSize = (int) Math.floor(Math.sqrt(arrayToSearch.length));

    int currentLastIndex = blockSize-1;
    
    // Jump to next block as long as target element is > currentLastIndex
    // and the array end has not been reached
    while (currentLastIndex < arrayToSearch.length && element > arrayToSearch[currentLastIndex]) {
        currentLastIndex += blockSize;
    }

    // Find accurate position of target element using Linear Search
    for (int currentSearchIndex = currentLastIndex - blockSize + 1;
         currentSearchIndex <= currentLastIndex && currentSearchIndex < arrayToSearch.length; currentSearchIndex++) {
        if (element == arrayToSearch[currentSearchIndex]) {
            return currentSearchIndex;
        }
    }
    // Target element not found. Return negative integer as element position.
    return -1;
}

First off, we've calculated the block size. Generally, a square root of the array's length is a good size to choose. This is further explained in the Big-O Analysis section. Searching through a block like this, in the end, will also be cheap for an algorithm like Linear Search.

Since the array is sorted, if our target element's value is greater than the value of the current element, then the target element surely cannot be inside the current block. So we jump to the next block and compare the target element with the new block’s last index element value.

This jump is repeated until the block that contains the target element is found.

If the target element is no longer greater than the value of the last element in a block, then it has to be inside the block if it exists at all.

So we will find the accurate position of the target element using Linear Search

If we reach the end of the array without finding a block that contains our target element - it's not present in the array and we return -1 to signify that.

Recursive Implementation

With the iterative implementation out of the way, let's explore the recursive implementation as well:

public static int jumpSearchInit(int[] arrayToSearch, int element) {
    int blockSize = (int) Math.sqrt(arrayToSearch.length);

    // Hold the last index of the current block
    int currentLastIndex = blockSize-1;

    return jumpSearch(arrayToSearch, element, blockSize, currentLastIndex);
}

public static int jumpSearch(int[] arrayToSearch, int element, int blockSize, int currentLastIndex) {
    if (currentLastIndex < arrayToSearch.length && element > arrayToSearch[currentLastIndex]) {
        currentLastIndex += blockSize;
        // Make recursive call to jumpSearch method
        return jumpSearch(arrayToSearch, element, blockSize, currentLastIndex);
    } else {
        // Find accurate position of target element using linear search
        for (int currentSearchIndex = currentLastIndex - blockSize + 1;currentSearchIndex <= currentLastIndex && currentSearchIndex < arrayToSearch.length; currentSearchIndex++) {
            if (element == arrayToSearch[currentSearchIndex]) {
                return currentSearchIndex;
            }
        }
    }
    // Target element not found. Return negative integer as element position.
    return -1;
}

Recursively performing a Jump Search works in the same way. We just call the method recursively instead of having a while loop.

We need the use of an initializer method to make some initial calculations. Namely, the optimum block size and the last index of the very first block.

Thereafter, for as long as our target element is greater than the current block’s last index element value, we recursively call Jump Search method passing the parameters of the subsequent block to it.

This recursion ends once the block containing the target element was found, or if the array end was reached eventually

In case such a target block was found, we perform a Linear Search on it to find the position of the target element.

Benchmarking Jump Search

Let’s benchmark Jump Search by running it against sorted integer arrays of varied sizes. Of course, we'll be searching for the worst-case scenario in all of these (the last element):

Compared to Linear Search which takes 5.4209ms, it's evident that Jump Search is significantly faster.

Big-O Analysis

Consider a sorted integer array of size n with a block size of m.

In the best case, Jump Search would find the target element at the edge of the very first block it searches in. In turn, this causes Jump Search to have a best-case efficiency of O(1) complexity in Big-O Notation terms.

By contrast, considering its worst case, Jump Search would consecutively jump to its very last block searching for the target element, in turn causing an n/m number of jumps. Additionally, if the last element’s value of this block was greater than the target element, Jump Search would perform a linear search with m-1 iterations.

This causes Jump Search to make (n/m) jumps with additional m-1 iterations. This value is minimum at m = √n. Therefore, the optimum block size is √n.

Accordingly, Jump Search maintains a worst and average case efficiency of O(√n) complexity.

This makes it noteworthy to mention that although Jump Search is highly efficient for searching arrays especially when its only-seeks-forward behavior is favorable - its average performance makes it sit somewhere between Binary Search with its O(log n) complexity and Linear Search with an O(n) complexity.

And also, Jump Search consistently requires its searched arrays to be sorted in ascending order, in advance.

Conclusion

Jump Search performs by jumping ahead block-by-block of the array until a block that might contain a given element is found.

In this article, we've implemented iterative and recursive Jump Search and benchmarked the algorithm with arrays of different sizes.

Furthermore, we undertook a Big-O Analysis proving how Jump Search acquired its average and worst-case efficiency of O(√n).