What is a jump search?

Computer systems perform different search operations to find any particular data. There are many search algorithms, and some of them are more optimal than others in certain contexts. The same is the case with linear and binary searches. Linear search works well only with small inputs, and binary search works better with large inputs. The jump search algorithm lies in between these algorithms.

In the jump search algorithm, the idea is to search fewer elements than linear search. As the name implies, it jumps to different blocks of elements and then finds the element in the block linearly.

Note: If n is the array size, then the block size would be square root of array size.
Block size = $\sqrt{n}$

Algorithm

A jump search algorithm finds a specific element in a sorted array. It makes the blocks of the array and searches the element in a block linearly.

If the element is smaller than the target element, jump to the next block.
If the element is greater than the target element, the target element is in the current block. Run a linear search in this block and find the element.
If the element is the target element, then just return it.

Example

Let's suppose we get a sorted array with 10 elements. The size of the block, in this case, would be 3. We need to search its element by using a jump search algorithm. Let's visualize how we can search an element with the help of the jump search algorithm.

#include<iostream>
#include<cmath>
using namespace std;
int jump_Search(int array[], int array_size, int element) {
   int i = 0;
   int block = sqrt(array_size); // initializing block size= √(n)
   while(array[block] <= element && block < array_size) { 
      i = block; // shift the block
      block += sqrt(array_size);
      if(block > array_size - 1)  // if block size exceeds the array size
         return -1; 
   }
   for(int j = i; j<block; j++) { // linear search in current block
      if(array[j] == element)
         return j; // position of element being searched 
   }
   return -1;
}
int main() {
   int size, element, index;
   int array[] = { 0,1,3, 5, 7, 13, 21,
                43, 55, 62};
    element = 55;
    size = sizeof(array) / sizeof(array[0]);
   index = jump_Search(array, size, element);
   
   if(index>=0)
      cout << "\n Element is found at index: " << index;
   else
      cout << "\n Element is not found in the list.";
}

Explanation

Lines 5–7: We define jump_search() function to perform the jump search algorithm. We initialize i as loop variable and block which is the size of the block.

Lines 9–14: In while loop condition, we check the block size should not exceed the array size, and the current element array[block] should be less than the element to be found. Afterward, we shift to next block for next iteration. We return -1 if the block size exceeds the array size.

Lines 16–21: We create a for loop for linear search in the block. Then, we return the element after finding it.

Time complexity: The time complexity of the jump search is $O(\sqrt{n})$ where $n$ is the size of the array.

Space complexity: The space complexity of the jump search is $O(1)$ .

Note: The time complexity of jump search lies in between linear search $O(n)$ and binary search $O(log (n))$ .

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

What is a jump search?

Algorithm

Example

Implementation

Explanation