2
\$\begingroup\$

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)
\$\endgroup\$
2
  • \$\begingroup\$ Can you add the import on top of the file, plus remove the unnessary 1 at then end of the file. \$\endgroup\$ Commented Oct 25, 2017 at 14:32
  • \$\begingroup\$ Done, well 1 was the output \$\endgroup\$ Commented Oct 25, 2017 at 14:33

2 Answers 2

Reset to default
1
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ That's interesting, my function is almost taking 2x with yours ( pretty refined version you illustrated ) Let me try at my end :) Thanks @Ludisposed :) \$\endgroup\$ Commented Oct 25, 2017 at 14:56
1
\$\begingroup\$

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")
\$\endgroup\$
6
  • \$\begingroup\$ I think return -1 for fail is the best option \$\endgroup\$ Commented Oct 25, 2017 at 14:51
  • \$\begingroup\$ 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 ? \$\endgroup\$ Commented Oct 25, 2017 at 14:52
  • \$\begingroup\$ That is really cleaner this approach ... about the proper implementation of the algo, I will hopefully check once back at home :) @TarunK \$\endgroup\$ Commented Oct 25, 2017 at 14:54
  • \$\begingroup\$ 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 \$\endgroup\$ Commented Oct 30, 2017 at 11:30
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Oct 30, 2017 at 11:38

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.