Jump Search Algorithm

import math

def jump_search(arr, target):
    """
    Jump Search Algorithm
    Time Complexity: O(√n)
    Space Complexity: O(1)
    Prerequisite: Array must be sorted
    """
    n = len(arr)
    
    # Finding the optimal jump size (√n)
    jump = int(math.sqrt(n))
    
    # Finding the block where element is present
    prev = 0
    while arr[min(jump, n) - 1] < target:
        prev = jump
        jump += int(math.sqrt(n))
        
        # If we have reached beyond the array
        if prev >= n:
            return -1
    
    # Linear search in the identified block
    while arr[prev] < target:
        prev += 1
        
        # If we reached next block or end of array
        if prev == min(jump, n):
            return -1
    
    # If element is found
    if arr[prev] == target:
        return prev
    
    return -1

# Example usage
sorted_array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31]
target = 15

result = jump_search(sorted_array, target)
if result != -1:
    print(f"Element {target} found at index {result}")
else:
    print(f"Element {target} not found")

# Optimal jump size calculation
optimal_jump = int(math.sqrt(len(sorted_array)))
print(f"Optimal jump size for array of length {len(sorted_array)}: {optimal_jump}")