SimuVedaAlgorithms Lab Open in the lab

Searching / Beginner

Jump Search Visualizer

On a sorted array, jump ahead √n values at a time until you pass the target, then walk back through that one block with a linear scan.

Start the Jump Search simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(1)
Average timeO(√n)
Worst timeO(√n)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Sorted 9 values, so jump √9 ≈ 3 at a time. Search for 63. [3, 8, 15, 23, 42, 51, 63, 77, 90]
  2. a[2] = 15 < 63, so the target is further right. Jump ahead.
  3. a[5] = 51 < 63, so the target is further right. Jump ahead.
  4. Reached the last block [6..8]. Scan it.
  5. a[6] = 63. Found it. Return 6.

Try it with your own input →

Jump search in Java, Python, C++, C and JavaScript

int jumpSearch(int[] a, int target) {
  int n = a.length, step = (int) Math.sqrt(n);
  int prev = 0, cur = step;
  while (cur < n && a[cur - 1] < target) {
    prev = cur;
    cur += step;
  }
  for (int i = prev; i < Math.min(cur, n); i++) {
    if (a[i] == target) return i;
  }
  return -1;
}
import math

def jump_search(a, target):
    n = len(a); step = int(math.sqrt(n))
    prev, cur = 0, step
    while cur < n and a[cur - 1] < target:
        prev = cur
        cur += step
    for i in range(prev, min(cur, n)):
        if a[i] == target:
            return i
    return -1
int jumpSearch(const vector<int>& a, int target) {
  int n = a.size(), step = (int)sqrt(n);
  int prev = 0, cur = step;
  while (cur < n && a[cur - 1] < target) {
    prev = cur;
    cur += step;
  }
  for (int i = prev; i < min(cur, n); i++) {
    if (a[i] == target) return i;
  }
  return -1;
}
#include <math.h>

int jumpSearch(int a[], int n, int target) {
  int step = (int)sqrt(n);
  int prev = 0, cur = step;
  while (cur < n && a[cur - 1] < target) {
    prev = cur;
    cur += step;
  }
  int end = cur < n ? cur : n;
  for (int i = prev; i < end; i++) {
    if (a[i] == target) return i;
  }
  return -1;
}
function jumpSearch(a, target) {
  const n = a.length, step = Math.floor(Math.sqrt(n));
  let prev = 0, cur = step;
  while (cur < n && a[cur - 1] < target) {
    prev = cur;
    cur += step;
  }
  for (let i = prev; i < Math.min(cur, n); i++) {
    if (a[i] === target) return i;
  }
  return -1;
}

In an interview

It sits between linear O(n) and binary O(log n). It only ever moves forward, which helps when going backwards is expensive, such as on a tape or a singly linked structure.

More searching