Jump Search Algorithm is a relatively new algorithm for searching an element in a sorted array.

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.

Let’s 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]

   

Jump Search with an Example

 Let us trace the above algorithm using an example:

Consider the following inputs:

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

Step 1: m = √n = 4 (Block Size)

Step 2: Compare A[0] with item. Since A[0] != item and A[0]<item, skip to the next block

       

Step 3: Compare A[3] with item. Since A[3] != itemand A[3]<item, skip to the next block

Step 4: Compare A[6] with item. Since A[6] != itemand A[6]<item, skip to the next block

Step 5: Compare A[9] with item. Since A[9] != itemand A[9]<item, skip to the next block

Step 6: Compare A[12] with item. Since A[12] != item and A[12] >item, skip to A[9]

(beginning of the current block) and perform a linear search.

  • Compare A[9] with Since A[9] != item, scan the next element
  • Compare A[10] with item. Since A[10] == item, index 10 is printed as the valid location and the algorithm will terminate