Jump Search Find an element in a sorted array. Worstcase Complexity: On rootn All items in list must be sorted like binary search Find block that contains target value and search it linearly in that block It returns a first target value in array reference: https:en.wikipedia.orgwikiJumpsearch return 1 means that array doesn't contain target value find block that contains target value find target value in block if there is target value in array, return it
import math

def jump_search(arr,target):
    """
    Worst-case Complexity: O(√n) (root(n))
    All items in list must be sorted like binary search

    Find block that contains target value and search it linearly in that block
    It returns a first target value in array

    reference: https://en.wikipedia.org/wiki/Jump_search
    """

    length = len(arr)
    block_size = int(math.sqrt(length))
    block_prev = 0
    block= block_size

    # return -1 means that array doesn't contain target value
    # find block that contains target value

    if arr[length - 1] < target:
        return -1
    while block <= length and arr[block - 1] < target:
        block_prev = block
        block += block_size

    # find target value in block

    while arr[block_prev] < target :
        block_prev += 1
        if block_prev == min(block, length) :
            return -1

    # if there is target value in array, return it

    if arr[block_prev] == target :
        return block_prev
    return -1
