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

Your email address will not be published. Required fields are marked *