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.
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).
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))
2 4 55 68 79 85 97 68
You may also read,