Jump search is a searching algorithm to find the position of a searched value in a sorted list by dividing the array into several fixed$-$size blocks, jumping

to the first index of the block, then comparing the value of the block's first index with the searched value. If the value of the block's first index is greater

than the searched value, it jumps backward to the previous block, then starts a linear search of the block.

For example:

Lets consider a sorted array A$[]$ of size $n,$ with indexing ranging between $0$ and $n-1,$ and element $x$ that needs to be searched in the array $A[].$ For

implementing this algorithm, a block of size $m$ is also required, that can be skipped or jumped in every iteration. Thus, the algorithm works as follows:

Iteration $1$: if $(x==A[]),$ then success, else, if $(x>A[]),$ then jump to the next block.

Iteration $2$: if $(x==A[m],$ then success, else, if $(x>A[m]),$ then jump to the next block.

Iteration $3$: if $(\_),$ then success, else, if $(x>A[2m],$ then jump to the next block.

At any point in time, if $(A[(k-1)m]A[km]x,$ then a linear search $is$ performed from index $A[(k-1)m]toA[km]$

Question:

Write a program $to$ implement the jump search algorithm and test the algorithm using a sorted array.