The Jump Search Algorithm is a very interesting question that you may have heard in your school or college asked in many interviews including FAANG companies.  


The idea behind this searching technique is to search fewer elements compared to a linear search algorithm (which scans every element in the array to check if it matches the element being searched or not). This can be done by skipping some fixed number of array elements or jumping ahead by a 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 array A[]. For implementing this algorithm, a block of size m is also required, which 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]

Let's start with the algorithm,

var jumpSearch = function(arr, target) {

  let len = arr.length

  //Finding the block size for the jump
  let step = Math.floor(Math.sqrt(len));

  //blockStart is the starting index of the block that our target will be in
  let blockStart = 0, currentStep = step;

  while (arr[Math.min(currentStep, len) - 1] < target)
  {
    //as long as we haven't found the block, we move to the next block and check again
    blockStart = currentStep;
    currentStep += step;

    //If the next block is pass the length of the array, target doesn't exist, return -1
    if (blockStart >= len)
      return -1;
  }

  //Linear Search within the block until we find the possible index for the target
  while (arr[blockStart] < target)
  {
    blockStart++;

    //If we reached the next block or end of array, the target doesn't exist
    if (blockStart == Math.min(currentStep, len))
      return -1;
  }

  //Check if the element is the target, if not, target doesn't exist.
  if (arr[blockStart] == target)
    return blockStart
  else
    return -1;
}

Here,

Let us trace the above algorithm using an example:

Input:

arr = [0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 77, 89, 101, 201, 256, 780];
target = 77


Step 1: step = √len = 4 (Block Size)

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





Step 3: Compare arr[3] with target. Since arr[3] != target and arr[3]< target, skip to the next block





Step 4: Compare arr[6] with target. Since arr[6] != target and arr[6]< target, skip to the next block





Step 5: Compare arr[9] with target. Since arr[9] != target and arr[9]< target, skip to the next block





Step 6: Compare arr[12] with target. Since arr[12] != target and arr[12]< target, skip to A[9] (beginning of the current block) and perform a linear search.






Compare arr[9] with target. Since arr[9] != target, scan the next element

Compare arr[10] with target. Since arr[10] == target, index 10 is printed as the valid location and the algorithm will terminate



I hope you understood the algorithm. If you have any doubts, please let us know in the comments.