Jump Search Visualizer

Target:

Speed:

SlowFast

Elements:

916

(12)

Jump Size: 3Phase: jumping

Jump Position

Search Block

Current Check

Target Value

Found

Operation Logs

No operations yet

Algorithm Info

Time Complexity: O(√n) - jump size is √n with linear search in block

Space Complexity: O(1) - uses constant extra space

Jump Size: √n (square root of array length)

Best Case: O(1) - target is at first jump position

Worst Case: O(√n) - target is at end of last block

Prerequisite: Array must be sorted in ascending order

How it works: Jump ahead by √n steps to find the right block, then linear search within that block.

When to use: Better than linear search but doesn't require sorted array knowledge like binary search.

Implementation

function jumpSearch(arr, target) {
  const n = arr.length;
  const jumpSize = Math.floor(Math.sqrt(n));
  let jumpIndex = 0;

  // Phase 1: Jump ahead to find the right block
  while (jumpIndex < n && arr[Math.min(jumpIndex, n - 1)] < target) {
    jumpIndex += jumpSize;
  }

  // Phase 2: Linear search in the identified block
  const blockStart = jumpIndex - jumpSize + 1;
  const blockEnd = Math.min(jumpIndex, n - 1);

  for (let i = Math.max(0, blockStart); i <= blockEnd; i++) {
    if (arr[i] === target) {
      return i; // Found!
    }
    if (arr[i] > target) {
      break; // Target not in array
    }
  }

  return -1; // Not found
}