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)

• Ludisposed: Can you add the import on top of the file, plus remove the unnessary 1 at then end of the file.
• Tarun K: Done, well 1 was the output

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

• Tarun K: That's interesting, my function is almost taking 2x with yours ( pretty refined version you illustrated ) Let me try at my end :) Thanks @Ludisposed :)

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")

• Ludisposed: I think return -1 for fail is the best option
• Tarun K: Well return value doesn't matter, if number is not found in list. I mean it can be 0, None or -1. My concern is, Is this the most optimized version of Jump search or can be improve ?
• Billal BEGUERADJ: That is really cleaner this approach ... about the proper implementation of the algo, I will hopefully check once back at home :) @TarunK
• Billal BEGUERADJ: IMHO, in case the key is not found, I think None is a better choice over -1 which could be confusing as, in Python, -1 corresponds to the last element of the list. @Ludisposed
• Ludisposed: You might have a point, but look at for instance the str.find() that return -1 when none is found. The function returns an int when found, so adhere the type and return -1 when not found. Either way, I think both are fine to use, might be just a question of preference.