Jump Search

{{This article was originally posted on December 22, 2016. My posts were lost and after being found I am re-posting them.}}

Few years ago (I think in 2013), I read this article on Jump Search : http://www.stoimen.com/blog/2011/12/12/computer-algorithms-jump-search/ Since the code presented was in php, got the urge to try it in Python. So wrote the code, forgot about it and discovered it in my hard drive few months ago. So putting it up as an archive. The Jump Search works as in picture below:

My Python code is as given below:

import math

def jumpSearch(noToSearch, lis):
    lenOfList = len(lis)
    prev = 0
    counter = 0
    step = int(math.floor(math.sqrt(lenOfList)))
    while lis[step if step < lenOfList else (lenOfList-1)] < noToSearch:
        prev = step
        print "Inside while : ", prev
        step = step + int(math.floor(math.sqrt(lenOfList)))
        counter = counter + 1
        print "Count : ", counter
        if step >= lenOfList:
            break
    while lis[prev] < noToSearch:
        prev = prev + 1
        counter = counter + 1
        print "Count : ", counter
    return prev+1

if __name__ == "__main__":
    lis = range(1,1000)
    print jumpSearch(624, lis)