Last day's algorithm which was a searching algorithm was much simpler to understand than the sorting algorithms I learned some days before and today I learned another simple algorithm which is also a searching algorithm. This algorithm is called Jump Search.
Jump Search Algorithm
Jump Search algorithm is a simple searching algorithm. Just like Binary Search it takes a sorted list as the input with the number element to look for. It searches through the list by jumping of a set number of elements from the list. It is a fairly simple algorithm to understand as well as to implement it.
How Jump Search Works?
Jump Search takes a sorted array as input with the element to look for. Let this element be x. Then it loops through the sorted array and jumps n elements until it finds the element that is bigger than x and also remembers the last element it jumped. After finding the element that is bigger than x it will perform a liner search between the last jumped element and the bigger element.
Linear search is also a searching algorithm which loops throuhg the whole list a checks every element until it find the one it was looking for. For worst case scenario Linear search takes O(n) time and in best case O(1) or contast time.
Implementation
The implementation below is done in Python.
import math
arr = [1,2,3,4,5,6,7,8,9]
X = 5
def jump_search(arr, num):
jmp = math.floor(math.sqrt(len(arr)))
jmp_prev = 0
while arr[jmp] < num:
jpm_prev = jmp
jmp += jmp
if jmp_prev > len(arr):
return
while arr[jmp_prev] < num:
jmp_prev += 1
if jmp_prev == jmp:
return
if arr[jmp_prev] == num:
return jmp_prev
return
res = jump_search(arr, X)
if res:
print(f"At Index: {res}")
else:
print(f"Num Not In List")
Time Comlpexity
The Time Complexity for Jump Search is O(√n) which is faster than Linear Searhc but Slower than the Binary search.
zainsci