Q3.

Write a Python program to perform Jump Search for a given key and report success or failure. Prompt the user to enter the key and a list of numbers.

-----------------------------------------------------------------------------------------------------------------------------

Similar to Binary Search, Jump Search or Block Search is an algorithm only for ordered (sorted) lists. The major idea behind this algorithm is to make less comparisons by skipping a definite amount of elements in between the elements getting compared leading to less time required for the searching process.

It can be classified as an improvement of the linear search algorithm since it depends on linear search to perform the actual comparison when searching for a value.

-----------------------------------------------------------------------------------------------------------------------------

Jump Search Steps

In Jump search, it is not necessary to scan all the elements in the list to find the desired value. We just check an element and if it is less than the desired value, then some of the elements following it are skipped by jumping ahead.

After moving a little forward again, the element is checked. If the checked element is greater than the desired value, then we have a boundary and we are sure that the desired value lies between the previously checked element and the currently checked element. However, if the checked element is less than the value being searched for, then we again make a small jump and repeat the process.

Given a sorted list, instead of searching through the list elements incrementally, we search by jump. The optimal size for jump is $\sqrt{N}$ where the N is the length of the list.

So in our input list list_of_numbers, if we have a jump size of jump then our algorithm will consider the elements between list_of_numbers[0] and list_of_numbers[0 + number_of_jumps], if the key element is not found then we will consider the other elements between list_of_numbers[0 + number_of_jumps] and list_of_numbers[0 + 2*number_of_jumps], again if the key element is not found then we consider the elements between list_of_numbers[0 + 2*number_of_jumps], and list_of_numbers[0 + 3*number_of_jumps] and so on.

With each jump, we store the previous value we looked at and its index. When we find a set of values where list_of_numbers[i] < key_element < list_of_numbers[i + number_of_jumps], we perform a linear search with list_of_numbers[i] as the left-most element and list_of_numbers[i + number_of_jumps] as the right-most element in our search block.

For example, consider a list of [1, 2, 3, 4, 5, 6, 7, 8, 9].The length of the list is 9 and the size of jump is 3. If we have to find the key element 8 then the following steps are performed using the Jump search technique.

Step 1: First three elements are checked. Since 3 is smaller than 8, we will have to make a jump ahead.

jump1

Step 2: Next three elements are checked. Since 6 is smaller than 8, we will have to make a jump ahead.

jump1

Step 3: Next three elements are checked. Since 9 is greater than 8, the desired value lies within the current boundary.

jump1

Step 4: A linear search is now done to find the value in the array.

-----------------------------------------------------------------------------------------------------------------------------

In [8]:
import math


def jump_search(list_of_numbers, key):
    list_length = len(list_of_numbers)

    # Calculate jump size
    jump = int(math.sqrt(list_length))

    left, right = 0, 0  # These are the index values

    # Find the block where key element is present (if it is present)
    while left < list_length and list_of_numbers[left] <= key:
        right = min(list_length - 1, left + jump)
        if list_of_numbers[left] <= key <= list_of_numbers[right]:
            break
        left += jump

    if left >= list_length or list_of_numbers[left] > key:
        return -1

    right = min(list_length - 1, right)
    i = left
    # Do linear search for key element in the block
    while i <= right and list_of_numbers[i] <= key:
        if list_of_numbers[i] == key:
            return i  # Return the position of the key element
        i += 1

    return -1


def user_input():
    list_of_numbers = list()
    total_elements = input("Enter a list of numbers in ascending order with space between each other: ").split()
    for each_element in range(len(total_elements)):
        list_of_numbers.append(int(total_elements[each_element]))

    key = int(input("Enter the Key number to search: "))

    index = jump_search(list_of_numbers, key)
    if index == -1:
        print("Entered key is not present")
    else:
        print(f"Key number {key} is found in Position {index + 1}")


if __name__ == "__main__":
    user_input()
Enter a list of numbers in ascending order with space between each other: 1 2 3 4 5 6 7 8 9
Enter the Key number to search: 8
Key number 8 is found in Position 8

-----------------------------------------------------------------------------------------------------------------------------

Step by Step tracing of the above code

Elements -> 1 2 3 4 5 6 7 8 9
Index    -> 0 1 2 3 4 5 6 7 8

left = 0
right = 0
list_length = 9
jump = 3

while 0 < 9 and 1 <= 8:
    right = min(8, 3)
    right is 3
    if 1 <= 8 <= 4 condition is False
    left = 3

while 3 < 9 and 4 <= 8:
    right = min(8, 6)
    right is 6    
    if 4 <= 8 <= 7: condition is False
    left = 6

while 6 < 9 and 7 <= 8:
    right = min(8, 9)
    right is 8
    if 7 <= 8 <= 9: condition is True
    break

right = min(8, 8)
right is 8
i = left
i is 6

while 6 <= 8 and 7 <= 8:
    if 7 == 8: condition is False
    i += 1
    i is 7

while 7 <= 8 and 8 <= 8:
    if 8 == 8:  condition is True
        return 7 here 7 is the index position and not the actual element

print -> i + 1 position