Back to Searching

Jump Search Visualizer

Watch how Jump Search combines the efficiency of jumping with linear search to find elements in sorted arrays.

Time: O(√n)
Space: O(1)
Requirement: Sorted Array
Jump + Linear
Jump Size: √15 = 3 | Phase: JUMPING | Comparisons: 0
0
1
1
3
2
5
3
7
4
9
5
11
6
13
7
15
8
17
9
19
10
21
11
23
12
25
13
27
14
29
Target: 15 | Step: 1 of 0

Current Step:

Click Start to begin Jump Search visualization

Jump Search

Time Complexity:O(√n)
Space Complexity:O(1)
Jump Size:√n
Type:Hybrid

Color Legend

Jumping Phase
Linear Search Phase
Search Block
Target Found
Not in Search Range

How It Works

  1. 1Calculate jump size as √n
  2. 2Jump by step size until element ≥ target
  3. 3Perform linear search in identified block
  4. 4Return index if found, -1 otherwise

Python Implementation

import math

def jump_search(arr, target):
    n = len(arr)
    step = int(math.sqrt(n))
    prev = 0
    
    # Jumping phase
    while arr[min(step, n) - 1] < target:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1
    
    # Linear search phase
    while arr[prev] < target:
        prev += 1
        if prev == min(step, n):
            return -1
    
    if arr[prev] == target:
        return prev
    
    return -1

Real-world Applications

  • • Searching large sorted datasets
  • • When binary search overhead is too high
  • • Searching in systems with sequential access
  • • Optimal for arrays where jumping is efficient
  • • Database indexing with block-based storage
  • • Finding data in sorted file systems