Jump Search

Color Legend

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