# Implementing Jump Search algorithm in Python

In this tutorial, we will learn about the standard **Jump search algorithm in Python** and will implement it in Python.

**Jump Search in Python**

Similar to Binary Search,** Jump **or **block search** is an algorithm only for ordered (sorted) lists. The major idea behind this algorithm is to make less comparisons by skipping a definite amount of elements in between the ones getting compared leading to less time required for the searching process.

**The ideal number of elements to be skipped**

Keeping in mind the **worst case scenario**, we have to jump n/p elements and if in case the last value compared is greater than the element we are searching for; after that, we are required to perform p-1 comparisons going on each element one by one from the back.

Then the total number of comparisons, in this case, will be ((n/p) + p-1). The solution of the equation ((n/p) + p-1) will be minimum when p = √n leading the optimum stepping size to be **p = √n.**

**Space Complexity**

Jump Search takes constant space irrespective of the number of elements in the array taking the space required to be of the range O(1).

**Time Complexity**

The time complexity of the above algorithm is O(√n), where n is the number of elements in the list.

**Implementation of Jump Search**

import math list1= list(map(int ,input().split())) val=int(input()) gap = math.sqrt(len(list1)) left = 0 while(list1[int(min(gap, len(list1))-1)]<val): left = gap gap = gap + math.sqrt(len(list1)) if(left>=len(list1)): break while(list1[int(left)]<val): left =left + 1 if(left== min(gap, len(list1))): break if(list1[int(left)]==val): print(int(left))

**INPUT :**

2 4 55 68 79 85 97 68

**OUTPUT :**

3

You may also read,

## Leave a Reply