Jump search

Jump search (also known as block search) is an algorithm for finding the position of an element in a sorted array. Unlike linear search, it doesn't compare each element of an array with the target value. Instead, to find the target value, we can represent the array as a sequence of blocks:

The optimal block size is $\sqrt(n)$, where $n$ is the size of the array. In this case, the algorithm performs $\sqrt(n) + \sqrt(n)$ comparisons in the worst case, so the time complexity is $O(\sqrt(n))$. This algorithm is more efficient than the linear search algorithm.

Basic principles

Jump search is an algorithm designed for efficiently searching in sorted arrays, whether they are in ascending or descending order. Here are the fundamental principles:

Principle 1: In ascending sorted arrays, any value within a specific block is less than or equal to any value in the following block.

Principle 2: In ascending sorted arrays, if the target element is not found at the start of the first block (i.e., the first element of the array), and the left boundary of that block (i.e., the first element of the array) exceeds the target element, then the target element is not present in the array.

This means that if the target element is smaller than the left boundary of the first block, you don't need to search further because it cannot exist in the array due to the sorted nature of the array.

The essence of the algorithm lies in jumping over blocks to locate the block that might contain the target element efficiently.

Searching process

If the right border of a block is equal to the target element, we have found that element in the array. Sometimes we need to search the target with the minimum index.

If the right border of a block is greater than the target element, we have found the block that may contain the target value. When we have found such a block, the algorithm performs backward linear search within that block. If it has found the target value, it returns its index; otherwise, the array does not contain the target value.

Sometimes blocks don't include the first array element, and then the algorithm works in the same way as described above. It's because the first thing we do at the start of the algorithm is to check the first array element (Principle 2). And the complexity of the algorithm doesn't change.

Further, we will consider the algorithm with the jump size equal to $\sqrt(n)$.

Please keep in mind the following:

• If $\sqrt(n)$ is not an integer value, we take only the integer part, using the floor function;
• If the index of the next element to jump to is greater than the last array element index, we jump to the last array element index.

Example

Suppose we have a sorted ascending array of nine integers:

The input array has nine elements with indices from $1$ to $9$. We want to find the index of the value $26$ implementing jump search.

Our first step would be finding the block that may contain the target value. The jump length is $\sqrt(9) = 3$.

1) The first element (10) is less than the target value (26), so we jump to the next element with the index $1 + 3 = 4$.

2) The element with the index $4$ (20) is less than the target value (26); we jump to the next element with the index $4+ 3 = 7$.

3) The element with the index $7$ (30) is greater than the target value (26).

During the stage, we store indices of the current and the previously considered element to use them in the second stage.

Second, we perform a backward linear search.

We have the left and the right indices of the block that may contain the target value. The left is k2, the right is k3. Now we will consider only the elements belonging to this block.

After finishing linear search between these indices, we have found our element (26) and its index, $6$.

Thus, the idea is that the algorithm finds the blocks where the target element may be present and then uses linear search within the block.

Pseudocode of the jump search function

function jump_search(array, value):
    if array.isEmpty() then:             // if the array is empty
        return -1                        // there is no chance of finding the element
    
    curr = 1                             // current position, to begin with is 1
    prev = 1                             // keep track of previous position
    last = len(array)                    // last element of the array
    step = floor(sqrt(last))             // size of blocks

    while array[curr] < value:           // moving from block to block
        if curr == last then:            // if we have reached the end, and still not found
            return -1                    // it means the element is not in the array
        prev = curr                      // store position before moving forward
        curr = min(curr + step, last)    // move to the next block or the last element if we already are in the last block

    while array[curr] > value:           // performing backwards linear search until we find it
        curr = curr - 1                  // move backwards
        if curr <= prev then:             // if we move to the previous block and still not found 
            return -1                    // it means the element is not there

    if array[curr] == value:          // if there is a match
        return curr                      // it means we found the element

    return -1                            // the element is not in the array

Harder, faster, stronger

In this algorithm, once we find the block that may contain the value, we perform a backward linear search. However, what we could also do is perform another jump search within the block (backward or forward) and then perform jump search recursively until we have only one element.

This version will perform $\sqrt(n) + \sqrt(\sqrt(n)) + \sqrt(\sqrt(\sqrt(n))) + ... + 1$ comparisons in the worst case. It's faster than the base implementation, but is still $O(\sqrt(n))$.

Conclusion

This topic has hopefully made it clear to you what the jump search algorithm is and how it works. Let's recap the main points made above:

• We use jump search to find an element's position in a sorted array;
• The algorithm divides the array into several blocks and compares the right border of the blocks sequentially with the target element, in order to find the block that might contain it; then it performs backward linear search within that block to find the target element;
• Its time complexity is $O(\sqrt(n))$.