Jump

Jump Search algorithm is a slightly modified version of the linear search algorithm.

The main idea behind this algorithm is to reduce the time complexity by comparing lesser elements than the linear search algorithm.

The input array is hence sorted and divided into blocks to perform searching while jumping through these blocks.

For example, let us look at the given example below; the sorted input array is searched in the blocks of 3 elements each.

The desired key is found only after 2 comparisons rather than the 6 comparisons of the linear search.

Here, there arises a question about how to divide these blocks. To answer that, if the input array is of size ‘n’, the blocks are divided in the intervals of √n. First element of every block is compared with the key element until the key element’s value is less than the block element. Linear search is performed only on that previous block since the input is sorted. If the element is found, it is a successful search; otherwise, an unsuccessful search is returned.

Jump search algorithm is discussed in detail further into this chapter.

Jump Search Algorithm

The jump search algorithm takes a sorted array as an input which is divided into smaller blocks to make the search simpler. The algorithm is as follows −

Step 1 − If the size of the input array is ‘n’, then the size of the block is √n. Set i = 0.

Step 2 − The key to be searched is compared with the ith element of the array. If it is a match, the position of the element is returned; otherwise i is incremented with the block size.

Step 3 − The Step 2 is repeated until the ith element is greater than the key element.

Step 4 − Now, the element is figured to be in the previous block, since the input array is sorted. Therefore, linear search is applied on that block to find the element.

Step 5 − If the element is found, the position is returned. If the element is not found, unsuccessful search is prompted.

pseudocode:

function jumpSearch(arr, target):
    n = length of arr
    step = sqrt(n)  // Calculate the block size to jump
    
    // Finding the block where the target may be present
    prev = 0
    while arr[min(step, n) - 1] < target:
        prev = step
        step += sqrt(n)
        if prev >= n:
            return NOT_FOUND
    
    // Doing linear search in the identified block
    while arr[prev] < target:
        prev += 1
        if prev == min(step, n):
            return NOT_FOUND
    if arr[prev] == target:
        return prev
    
    return NOT_FOUND

Analysis

The time complexity of the jump search technique is O(√n) and space complexity is O(1).

function jumpSearch(arr, target) {
    const n = arr.length;
    let step = Math.sqrt(n);
    let prev = 0;
    
    while (arr[Math.min(step, n) - 1] < target) {
        prev = step;
        step += Math.sqrt(n);
        if (prev >= n) {
            return -1;
        }
    }

    while (arr[prev] < target) {
        prev++;
        if (prev == Math.min(step, n)) {
            return -1;
        }
    }

    if (arr[prev] === target) {
        return prev;
    }

    return -1;
}

// Example usage:
const arr = [1, 3, 5, 7, 9, 11, 13, 15, 17];
const target = 11;
const index = jumpSearch(arr, target);
if (index !== -1) {
    console.log(`Element ${target} found at index ${index}.`);
} else {
    console.log(`Element ${target} not found in the array.`);
}