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.
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.
Step 2:
Next three elements are checked. Since 6 is smaller than 8, we will have to make a jump ahead.
Step 3:
Next three elements are checked. Since 9 is greater than 8, the desired value lies within the current boundary.
Step 4:
A linear search is now done to find the value in the array.
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
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