What is a Jump (or Block) 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.

The fundamental idea behind this searching technique is to search fewer number of elements compared to linear search algorithm (which scans every element in the array to check if it matches with the element being searched or not). This can be done by skipping some fixed number of array elements or jumping ahead by fixed number of steps in every iteration.

Lets consider a sorted array A[] of size n, with indexing ranging between 0 and n-1, and element x that needs to be searched in the array A[]. For implementing this algorithm, a block of size m is also required, that can be skipped or jumped in every iteration. Thus, the algorithm works as follows:

• Iteration 1: if (x==A[0]), then success, else, if (x > A[0]), then jump to the next block.
• Iteration 2: if (x==A[m]), then success, else, if (x > A[m]), then jump to the next block.
• Iteration 3: if (x==A[2m]), then success, else, if (x > A[2m]), then jump to the next block.
• At any point in time, if (x < A[km]), then a linear search is performed from index A[(k-1)m] to A[km]

Consider the following inputs:

• A[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 77, 89, 101, 201, 256, 780}
• item = 77

• The single most important advantage of jump search when compared to binary search is that it does not rely on the division operator (/).
• 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.