Jump Search

Jump Search is a search algorithm to find an element from a sorted list of items. This type of search is also known as block search, because the given array is split into blocks to apply the search. Jump Search applies to Linear Data Structures like Arrays and Hash Tables.

Jump Search has better performance than Linear Search, but is less efficient compared to Binary Search Algorithms. Time complexity of Jump Search is O_(√n) and space complexity is O₍₁₎.

Jump Search Uses

Jump search is only used rarely. The only advantage of Jump Search over Binary Search is that the backward traversal is required only once in Jump Search, but in Binary Search, back and forth traversal is required multiple times to find the middle nodes. So, in a system where backward traversals are costlier, there might be an advantage in using Jump Search, like if data is stored in tapes which requires frequent direction change for doing a Binary Search.
How Jump Search Works

Jump Search is also a divide and conquer method. Jump search works in two parts. First section splits the array into blocks and identifies which block can have the searched item. This is done by comparing the search key and the last element of each block.

Once the block is identified, a Linear Search is performed on the block to check if the item is present.

The blocks are usually of a size of √n, n is the length of the array. So if the array has 10 elements, as in below code samples, it will be split into four blocks, first three having 3 elements each and the last one with 1 element.

Check the below gif image to easily understand the search process.
Algorithm

Jump Search Algorithm flow is listed as below.

Input : A sorted list of elements.
Output : Element position, if found. Else not found message.
1. Start.
2. Set start = 0, blockSize = √arrayLength, end = blockSize - 1, pos = -1.
  start and end values now represents the first block.
3. Check if searched value within the array by comparing first and last elements.
  If true go to step 4, else to step 8.
4. Use a while loop to iterate the blocks.
5. If the current block last element < searched value and start pos < array length searched element can be present in the next block. Go to step 6.
  Else current block if the only possibility to find the searched item. Go to step 7.
6. Find start and end positions of next block. Go to step 5.
7. Block that can have the search value is identified. Exit while loop. Go to step 8.
8. Perform Linear Search using a for loop and check for the element and return the pos.
9. If pos > -1, element found. Display result.
10. Else if pos = -1, element not found. Display not found message.
11. Stop.

Code Samples

Below are few sample code implementations of Jump Search Algorithm in Python, Java, C# and JavaScript.

import math

arry = [10, 12, 15, 19, 22, 25, 28, 30, 35, 40]
find = 35
pos = -1

start = 0
blockSize = int( math.sqrt(len(arry)) )
end = blockSize - 1

#Check algorithm section if any clarification needed in the logic
if not (find < arry[0] or find > arry[-1]):
    while arry[end] < find and start < len(arry):
        start = end + 1
        if( (end + blockSize) <= (len(arry)-1) ):
            end = end + blockSize
        else:
            end = len(arry)-1
    
    for i in range(start, end+1):
        if(arry[i] == find):
            pos = i
            break

if(pos > -1):
    print("Element found at position : ", pos)
else:
    print("Element not found")

class JumpSearch   
{
    public static void main(String[] args)   
    {  
        int arry[] = {10, 12, 15, 19, 22, 25, 28, 30, 35, 40};
        int find = 35;
        int pos = -1;

        int start = 0;
        int blockSize = (int)Math.sqrt(arry.length);
        int end = blockSize - 1;

        //Check algorithm section if any clarification needed in the logic
        if (!( find < arry[0] || find > arry[arry.length-1] )) {
            while (arry[end] < find && start < arry.length) {
                start = end + 1;
                if( (end + blockSize) <= (arry.length-1) )
                    end = end + blockSize;
                else
                    end = arry.length-1;
            }
            
            for (int i = start; i <= end; i++) {
                if(arry[i] == find) {
                    pos = i;
                    break;
                }
            }
        }

        if(pos > -1)
            System.out.println("Element found at position : " + pos);
        else
            System.out.println("Element not found");
    }
}

using System;
using System.Threading;

namespace DSA
{
   class Program
   {
       static void Main(string[] args)
       {
           int[] arry = { 10, 12, 15, 19, 22, 25, 28, 30, 35, 40 };
           int find = 35;
           int pos = -1;

           int start = 0;
           int blockSize = (int)Math.Sqrt(arry.Length);
           int end = blockSize - 1;

           //Check algorithm section if any clarification needed in the logic
           if (!(find < arry[0] || find > arry[arry.Length - 1]))
           {
               while (arry[end] < find && start < arry.Length)
               {
                   start = end + 1;
                   if ((end + blockSize) <= (arry.Length - 1))
                       end = end + blockSize;
                   else
                       end = arry.Length - 1;
               }

               for (int i = start; i <= end; i++)
               {
                   if (arry[i] == find)
                   {
                       pos = i;
                       break;
                   }
               }
           }

           if (pos > -1)
               Console.Write("Element found at position : " + pos);
           else
               Console.Write("Element not found");

           Thread.Sleep(5000);
       }
   }
}

function jumpSearch(find) {
    var arry = [ 10, 12, 15, 19, 22, 25, 28, 30, 35, 40 ];

    var find = 35;
    var pos = -1;

    var start = 0;
    var blockSize = Math.floor( Math.sqrt(arry.length) );
    var end = blockSize - 1;

        //Check algorithm section if any clarification needed in the logic
        if (!( find < arry[0] || find > arry[arry.length-1] )) {
            while (arry[end] < find && start < arry.length) {
                start = end + 1;
                if( (end + blockSize) <= (arry.length-1) )
                    end = end + blockSize;
                else
                    end = arry.length-1;
            }
            
            for (let i = start; i <= end; i++) {
                if(arry[i] == find) {
                    pos = i;
                    break;
                }
            }
        }

    if (pos > -1)
        alert("Element found at position : " + pos);
    else
        alert("Element not found");
    return false;
}

var find = 35;
jumpSearch(find);

Jump Search

Jump Search Uses

How Jump Search Works

Algorithm

Code Samples