CODEWITHSUNDEEP
pythonalgorithmsearch
MechaKondor
MechaKondor

Reputation: 69

Python Jump Search algorithm not returning one number

I'm trying to implement a jump search algorithm. However, in this example below, I cannot find the number of 72, even though it is clearly in the list that I defined. Here is the code, can someone explain to me why the rest of the numbers can be returned, but not 72 which is at position index 0 on the list?

def jumpSearch(list, number, constant) :
    i = 0
    counter = 0
    while (list[i] < number and i + constant < len(list) and list[i + constant] < number) :
        i = i + constant

    for j in range (i, i + constant, 1) :
        if (list[j] == number) :
            return list[j]
    return None

mylist = [72, 56, 93, 8, 22, 41, 88, 23, 60]
mylist.sort()
print(jumpSearch(mylist, 72, 3))

I have seen other examples on the net, however, I really wanted to test my own abilities at writing code and logic from scratch in order to get the result.

So my rudimentary understanding of jump search is preventing me from knowing whether or not this is a 'correct' way of doing a jump search. Any evaluation or improvements to the code or even a sample of the 'optimal and right' way of writing a jump search would be valuable to my learning!

Upvotes: 3

Views: 261

Answers (3)

7stud
7stud

Reputation: 48599

I added some debugging output to your function, so that you can see what's going on:

def jumpSearch(mylist, number, constant):
    i = 0
    counter = 0

    while (mylist[i] < number 
          and i + constant < len(mylist)
          and mylist[i + constant] < number):

        format_str= "In while:\n\t mylist[{}]={},number={},i+constant={},len(mylist)={},mylist[i+constant]={}"

        print( 
            format_str.format(
                i,
                mylist[i], 
                number,
                constant,
                len(mylist),
                mylist[i+constant]
            )
        )


        i = i + constant
        print("\t i={},mylist[{}+3]={},number={}".format(i,i,mylist[i+3],number))


    for j in range (i, i + constant, 1):

        f_string =  "In for:\n\t j={},i={},i+constant={},mylist[{}]={},number={}"
        print( f_string.format(j, i, i+constant, j, mylist[j], number))

        if (mylist[j] == number) :
            return mylist[j]

    return None

mylist = [72, 56, 93, 8, 22, 41, 88, 23, 60]
mylist.sort() #=> [8, 22, 23, 41, 56, 60, 72, 88, 93]
print(jumpSearch(mylist, 72, 3))

--output:--
In while:
     mylist[0]=8,number=72,i+constant=3,len(mylist)=9,mylist[i+constant]=41
     i=3,mylist[3+3]=72,number=72
In for:
     j=3,i=3,i+constant=6,mylist[3]=41,number=72
In for:
     j=4,i=3,i+constant=6,mylist[4]=56,number=72
In for:
     j=5,i=3,i+constant=6,mylist[5]=60,number=72
None

You can see that the while loop only executes once. The second line of output for the while loop shows that mylist[3+3] is equal to number and the next iteration of the while loop tests whether mylist[6] < number, which is false. So, execution jumps down to the for-loop, and the output shows that the for loop never finds a mylist[j] that is equal to 72

Upvotes: 0

Martijn Pieters
Martijn Pieters

Reputation: 1121834

If you look at your while loop you'll see that what happens when list[i + constant] is no longer smaller than 72:

while (... list[i + constant] < number):

You increment when list[i + constant] is smaller, not when equal or larger.

So we know that the value is between list[i] and list[i + constant] inclusive. However, range() produces numbers exclusive the end value. From the range() documentation:

For a positive step, the contents of a range r are determined by the formula r[i] = start + step*i where i >= 0 and r[i] < stop.

(Bold emphasis mine).

So you have an off-by-one error. The last value produced by the range() is i + constant - 1, and 72 is found at i + constant instead.

You need to add one to your end value and search through range(i, i + constant + 1):

for j in range (i, i + constant + 1):

Upvotes: 1

Rockybilly
Rockybilly

Reputation: 4510

The index of 72 is exactly on one of the steps (6 in your case, and your steps are 3), and you miss it because you used a < instead of <= sign.

Change list[i + constant] < number to list[i + constant] <= number.

Upvotes: 0

Related Questions