Repository navigation
Expand file tree
/
Copy pathjump_search.py
More file actions
35 lines (27 loc) · 1.54 KB
/
Copy pathjump_search.py
File metadata and controls
35 lines (27 loc) · 1.54 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import math
from src.algorithm_theory.linear_search import linear_search
def jump_search(array: list[int], target: int) -> int | None:
"""Jump Search (https://www.geeksforgeeks.org/jump-search/).
A searching algorithm for sorted arrays. The basic idea is to check fewer elements (than linear
search) by jumping ahead by fixed steps or skipping some elements in place of searching all elements.
For example, suppose we have an array arr[] of size n and block (to be jumped) size `m`. Then we search
at the indexes `arr[0]`, `arr[m]`, `arr[2m]…..arr[km]`, and so on. Once we find the interval
(`arr[km] < x < arr[(k+1)m]`), we perform a linear search operation from the index `km` to find `x`.
What is the optimal block size to be skipped?
In the worst case, we have to do `n/m` jumps and if the last checked value is greater than the element
to be searched for, we perform `m-1` comparisons more for linear search. Therefore the total number of
comparisons in the worst case will be `((n/m) + m-1)`. The value of the function `((n/m) + m-1)` will be
minimum when `m = √n`. Therefore, the best step size is `m = √n`. (Geeks For Geeks)
"""
length = len(array)
interval = int(math.sqrt(length))
index = interval - 1 # 0 Based
previous = index
while index <= length - 1:
if array[index] == target:
return index
if array[index] > target:
return linear_search(array, previous, index - 1, target)
previous = index
index += interval
return None