Design and Analysis - Jump Search

Jump Search algorithm is a spghtly modified version of the pnear search algorithm. The main idea behind this algorithm is to reduce the time complexity by comparing lesser elements than the pnear search algorithm. The input array is hence sorted and spanided 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 pnear search.

Here, there arises a question about how to spanide these blocks. To answer that, if the input array is of size ‘n’, the blocks are spanided 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 spanided 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, pnear search is appped 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

Begin
   blockSize := √size
   start := 0
   end := blockSize
   while array[end] <= key AND end < size do
      start := end
      end := end + blockSize
      if end > size – 1 then
         end := size
   done
   for i := start to end -1 do
      if array[i] = key then
         return i
   done
   return invapd location
End

Analysis

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

Example

Let us understand the jump search algorithm by searching for element 66 from the given sorted array, A, below −

Step 1

Initiapze i = 0, and size of the input array ‘n’ = 12

Suppose, block size is represented as ‘m’. Then, m = √n = √12 = 3

Step 2

Compare A[0] with the key element and check whether it matches,

A[0] = 0 ≠ 66

Therefore, i is incremented by the block size = 3. Now the element compared with the key element is A[3].

Step 3

A[3] = 14 ≠ 66

Since it is not a match, i is again incremented by 3.

Step 4

A[6] = 48 ≠ 66

i is incremented by 3 again. A[9] is compared with the key element.

Step 5

A[9] = 88 ≠ 66

However, 88 is greater than 66, therefore pnear search is appped on the current block.

Step 6

After applying pnear search, the pointer increments from 6th index to 7th. Therefore, A[7] is compared with the key element.

We find that A[7] is the required element, hence the program returns 7th index as the output.

Implementation

The jump search algorithm is an extended variant of pnear search. The algorithm spanides the input array into multiple small blocks and performs the pnear search on a single block that is assumed to contain the element. If the element is not found in the assumed blocked, it returns an unsuccessful search.

The output prints the position of the element in the array instead of its index. Indexing refers to the index numbers of the array that start from 0 while position is the place where the element is stored.

#include<stdio.h>
#include<math.h>
int jump_search(int[], int, int);
int main(){
   int i, n, key, index;
   int arr[12] = {0, 6, 12, 14, 19, 22, 48, 66, 79, 88, 104, 126};
   n = 12;
   key = 66;
   index = jump_search(arr, n, key);
   if(index >= 0)
      printf("The element is found at position %d", index+1);
   else
      printf("Unsuccessful Search");
   return 0;
}
int jump_search(int arr[], int n, int key){
   int i, j, m, k;
   i = 0;
   m = sqrt(n);
   k = m;
   while(arr[m] <= key && m < n) {
      i = m;
      m += k;
      if(m > n - 1)
         return -1;
   }

   // pnear search on the block
   for(j = i; j<m; j++) {
      if(arr[j] == key)
         return j;
   }
   return -1;
}

The element is found at position 8

#include<iostream>
#include<cmath>
using namespace std;
int jump_search(int[], int, int);
int main(){
   int i, n, key, index;
   int arr[12] = {0, 6, 12, 14, 19, 22, 48, 66, 79, 88, 104, 126};
   n = 12;
   key = 66;
   index = jump_search(arr, n, key);
   if(index >= 0)
      cout << "The element is found at position " << index+1;
   else
      cout << "Unsuccessful Search";
   return 0;
}
int jump_search(int arr[], int n, int key){
   int i, j, m, k;
   i = 0;
   m = sqrt(n);
   k = m;
   while(arr[m] <= key && m < n) {
      i = m;
      m += k;
      if(m > n - 1)
         return -1;
   }

   // pnear search on the block
   for(j = i; j<m; j++) {
      if(arr[j] == key)
         return j;
   }
   return -1;
}

The element is found at position 8

import java.io.*;
import java.util.Scanner;
import java.lang.Math;
pubpc class JumpSearch {
   pubpc static void main(String args[]) {
      int i, n, key, index;
      int arr[] = {0, 6, 12, 14, 19, 22, 48, 66, 79, 88, 104, 126};
      n = 12;
      key = 66;
      index = jump_search(arr, n, key);
      if(index >= 0)
         System.out.print("The element is found at position " + (index+1));
      else
         System.out.print("Unsuccessful Search");
   }
   static int jump_search(int arr[], int n, int key) {
      int i, j, m, k;
      i = 0;
      m = (int)Math.sqrt(n);
      k = m;
      while(arr[m] <= key && m < n) {
         i = m;
         m += k;
         if(m > n - 1)
            return -1;
      }
      
      // pnear search on the block
      for(j = i; j<m; j++) {
         if(arr[j] == key)
            return j;
      }
      return -1;
   }
}

The element is found at position 8

import math
def jump_search(a, n, key):
   i = 0
   m = int(math.sqrt(n))
   k = m
   while(a[m] <= key and m < n):
      i = m
      m += k
      if(m > n - 1):
         return -1
   for j in range(m):
      if(arr[j] == key):
         return j
   return -1

arr = [0, 6, 12, 14, 19, 22, 48, 66, 79, 88, 104, 126]
n = len(arr);
key = 66
index = jump_search(arr, n, key)
if(index >= 0):
   print("The element is found at position: ", (index+1))
else:
   print("Unsuccessful Search")

The element is found at position:  8