forked from Zircoz/Searching-Algos-in-Python
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Jump_Search.py
47 lines (38 loc) · 1.07 KB
/
Jump_Search.py
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
36
37
38
39
40
41
42
43
44
45
46
47
# Python3 Jump Search
# Complexity : O(sqrt(n))
import math
def jumpSearch( arr , x ):
# Finding block size to be jumped
n = len(arr)
step = math.sqrt(n)
# Finding the block where element is
# present (if it is present)
prev = 0
while arr[int(min(step, n)-1)] < x:
prev = step
step += math.sqrt(n)
if prev >= n:
return -1
# Doing a linear search for x in
# block beginning with prev.
while arr[int(prev)] < x:
prev += 1
# If we reached next block or end
# of array, element is not present.
if prev == min(step, n):
return -1
# If element is found
if arr[int(prev)] == x:
indices = []
while int(prev) < n and arr[int(prev)] == x:
indices.append(int(prev))
prev+=1
return indices
return -1
def main():
arr = [ 0, 1, 3, 4, 4, 5, 8, 13, 22, 24, 55, 59, 122, 213, 422, 555 ]
x = 55
index = jumpSearch(arr, x)
print("Number {} is at index {}".format(x,index))
if __name__ == "__main__":
main()