Python Jump Search algorithm not returning one number

Question

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!

Answer 1

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