Jump Search in Python

Question

I have implemented Jump search in Python, here is my code. Am I using the algorithm correctly ? Is there any pythonic way to achieve same ?

import math
def jump_search_2(arr,search):
    interval = int(math.sqrt(len(arr)))

    ''' find last lowest element '''
    for i in range(0,len(arr),interval):
        if arr[i] < search:
            low = i
        elif arr[i] == search:
            return i
        else:
            break
    ''' apply linear search '''
    l_index = [e for e,i in enumerate(arr[low:low+interval]) if i == search]
    if l_index[0]:
        return low+l_index[0]
    return "Not Found" 

Usage example:

arr = [ i for i in range(1,300,15)]
res = jump_search_2(arr, 16)
print(res)

Answer 1

The implementation definition of a Wikipedia Jump Search vs. your Jump Search

import math
import timeit

def jump_search_wiki(L, n, key):
    a, b = 0, int(n**.5)

    while L[min(b, n) - 1] < key:
        a = b
        b += int(n**.5)
        if a >= n:
            return -1

    while L[a] < key:
        a += 1

        if a == min(b, n):
            return -1

    if L[a] == key:
        return a

    return -1

def jump_search_2(arr,search):
    interval = int(math.sqrt(len(arr)))

    ''' find last lowest element '''
    for i in range(0,len(arr),interval):
        if arr[i] < search:
            low = i
        elif arr[i] == search:
            return i
        else:
            break
    ''' apply linear search '''
    l_index = [e for e,i in enumerate(arr[low:low+interval]) if i == search]
    if l_index[0]:
        return low+l_index[0]
    return "Not Found"


setup = "arr = [i for i in range(1,300,15)]"
print(min(timeit.Timer('a=arr[:];from __main__ import jump_search_2; jump_search_2(arr, 16)', setup=setup).repeat(7, 1000)))
print(min(timeit.Timer('a=arr[:];from __main__ import jump_search_wiki; jump_search_wiki(arr, len(arr), 16)', setup=setup).repeat(7, 1000)))

---

Timing results.

0.004113584203836659 -- Your jump search
0.0027036696179086606 -- Wiki jump search

Answer 2

For the moment, I did not dive into the details of your implementation, but one thing is obvious:

• When you find search, you return an integer value corresponding to its position.
• When you do not find it, you return a string .

This adds a little complication as how to call (and test) your function. But if you replace the returned string by None, it will be easier to call your function:

# Let us use your working example
if jump_search_2(arr, 16):
   # print("Found !")
else:
   # print("Not Found")
   # This is more pythonic than:
   # elif (jump_search_2(arr, 16) == "Not Found")