CODEWITHSUNDEEP
pythonalgorithm
Tarun K
Tarun K

Reputation: 499

Jump search algorithm in python

I am trying to implement jump search in python.

here is the code

'''
2 jump search
'''
import math
def jump_search(arr,search):
    interval = int(math.sqrt(len(arr)))
    for i in range(0,len(arr),interval):
        if arr[i] >  search:
            chunk = i
            break
        if arr[i] ==  search:
            return i
    arr_ls = arr[chunk-interval:chunk]
    ind = [i for i,d in enumerate(arr_ls) if d==search]
    return chunk-interval+ind[0]
arr = [ i for i in range(1,200,15)]

res = jump_search(arr, 121)
print(res)

here is the problems I am facing :

  1. last chunk is skipping
  2. Improved version ? Also i dont think my code clean and short

Upvotes: 0

Views: 2948

Answers (3)

Akshaya Natarajan
Akshaya Natarajan

Reputation: 2151

Can this be considered (not exactly an improvement) but as an alternate to the above code?

def jumpSearch(a,m,x):
    for i in range(0,len(a),m):
        if a[i]==x:
           return i
        elif a[i]>x:
           high = i
           break

    for j in range(high,high-m,-1):
        if a[j]==x:
           return j

Upvotes: 0

Miraj50
Miraj50

Reputation: 4407

Presently, if the search variable is present in the last chunk, then chunk won't be initialized. And hence, you must be getting an error. So why don't you check for the last interval specifically. I have added a flag variable which checks for that. If chunk is found, well and good, otherwise we have to see the last interval.

import math
def jump_search(arr,search):
    flag = 0
    interval = int(math.sqrt(len(arr)))
    for i in range(0,len(arr),interval):
        if arr[i] >  search:
            chunk = i
            flag = 1
            break
        if arr[i] ==  search:
            return i
    if flag==0:
        c=i
        for j in arr[i:]:
            if j==search:
                return c
            c+=1
    else:
        arr_ls = arr[chunk-interval:chunk]
        ind = [i for i,d in enumerate(arr_ls) if d==search]
        return chunk-interval+ind[0]
arr = [ i for i in range(1,200,15)]
res = jump_search(arr, 196)
print(res) 
# prints 13

Also, you won't have to do all this, if you keep track of the lower bound instead of the upper bound which you are doing now. So to make you code better, which you asked for, try this:

import math
def jump_search(arr,search):
    low = 0
    interval = int(math.sqrt(len(arr)))
    for i in range(0,len(arr),interval):
        if arr[i] < search:
            low = i
        elif arr[i] == search:
            return i
        else:
            break # bigger number is found
    c=low
    for j in arr[low:]:
        if j==search:
            return c
        c+=1
    return "Not found"

arr = [ i for i in range(1,200,15)]
res = jump_search(arr, 196)
print(res)
# prints 13

Upvotes: 3

Yaroslav Surzhikov
Yaroslav Surzhikov

Reputation: 1608

Your code skips last chunk, because step of for loop is greater than last chunk length. Also it would fail if you try search element which is not in list.

In summary - this should work for you:

import math


def jump_search(arr, search):
    interval = int(math.sqrt(len(arr)))
    i = 0
    # set i to zero if list is empty
    for i in range(0, len(arr), interval):
        if arr[i] > search:
            break
        if arr[i] == search:
            return i
    else:
        # if loop exited normaly - add interval to i, so last chuck is included too
        i += interval

    last_chunk = arr[i - interval:i]

    # iterate directly and simply break if item found
    for ind, val in enumerate(last_chunk):
        if val == search:
            break
    else:
        # if loop exited normaly - item not found in chunk
        # return None instead of index
        return None
    return i - interval + ind

Upvotes: 1

Related Questions