Jump Search

Algorithms

Jump search is a search algorithm for sorted arrays that works by jumping ahead by fixed steps and then performing a linear search in a smaller block.

Algorithm

The algorithm jumps ahead by a fixed step size (typically $n$ ), and when it finds a block where the target might be, it performs a linear search within that block.

Time Complexity

Jump search has a time complexity of $O (n)$ , where $n$ is the number of elements.

Implementation

import math

def jump_search(arr, target):
    n = len(arr)
    # Find the block size to jump
    step = int(math.sqrt(n))
    prev = 0
    
    # Jump ahead by step size
    while arr[min(step, n) - 1] < target:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1
    
    # Linear search within the block
    for idx in range(prev, min(step, n)):
        if arr[idx] == target:
            return idx
    
    return -1

# Example usage
if __name__ == "__main__":
    arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
    target = 15
    result = jump_search(arr, target)
    
    if result != -1:
        print("Element found at index {}".format(result))
    else:
        print("Element not found")