-
Notifications
You must be signed in to change notification settings - Fork 0
/
interpolation_search.py
90 lines (75 loc) · 2.67 KB
/
interpolation_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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
def interpolation_search(sorted_collection, item):
left = 0
right = len(sorted_collection) - 1
while left <= right:
if sorted_collection[left] == sorted_collection[right]:
if sorted_collection[left] == item:
return left
else:
return None
point = left + ((item - sorted_collection[left]) * (right - left)) // (
sorted_collection[right] - sorted_collection[left]
)
if point < 0 or point >= len(sorted_collection):
return None
current_item = sorted_collection[point]
if current_item == item:
return point
else:
if point < left:
right = left
left = point
elif point > right:
left = right
right = point
else:
if item < current_item:
right = point - 1
else:
left = point + 1
return None
def interpolation_search_by_recursion(sorted_collection, item, left, right):
if sorted_collection[left] == sorted_collection[right]:
if sorted_collection[left] == item:
return left
else:
return None
point = left + ((item - sorted_collection[left]) * (right - left)) // (
sorted_collection[right] - sorted_collection[left]
)
if point < 0 or point >= len(sorted_collection):
return None
if sorted_collection[point] == item:
return point
elif point < left:
return interpolation_search_by_recursion(sorted_collection, item, point, left)
elif point > right:
return interpolation_search_by_recursion(sorted_collection, item, right, left)
else:
if sorted_collection[point] > item:
return interpolation_search_by_recursion(
sorted_collection, item, left, point - 1
)
else:
return interpolation_search_by_recursion(
sorted_collection, item, point + 1, right
)
def __assert_sorted(collection):
if collection != sorted(collection):
raise ValueError("Collection must be ascending sorted")
return True
if __name__ == "__main__":
import sys
debug = 0
if debug == 1:
collection = [10, 30, 40, 45, 50, 66, 77, 93]
try:
__assert_sorted(collection)
except ValueError:
sys.exit("Sequence must be ascending sorted to apply interpolation search")
target = 67
result = interpolation_search(collection, target)
if result is not None:
print(f"{target} found at positions: {result}")
else:
print("Not found")