forked from TheAlgorithms/Python
-
Notifications
You must be signed in to change notification settings - Fork 0
/
interpolation_search.py
140 lines (119 loc) · 4.55 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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
"""
This is pure Python implementation of interpolation search algorithm
"""
def interpolation_search(sorted_collection, item):
"""Pure implementation of interpolation search algorithm in Python
Be careful collection must be ascending sorted, otherwise result will be
unpredictable
:param sorted_collection: some ascending sorted collection with comparable items
:param item: item value to search
:return: index of found item or None if item is not found
"""
left = 0
right = len(sorted_collection) - 1
while left <= right:
# avoid divided by 0 during interpolation
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]
)
# out of range check
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):
"""Pure implementation of interpolation search algorithm in Python by recursion
Be careful collection must be ascending sorted, otherwise result will be
unpredictable
First recursion should be started with left=0 and right=(len(sorted_collection)-1)
:param sorted_collection: some ascending sorted collection with comparable items
:param item: item value to search
:return: index of found item or None if item is not found
"""
# avoid divided by 0 during interpolation
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]
)
# out of range check
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):
"""Check if collection is ascending sorted, if not - raises :py:class:`ValueError`
:param collection: collection
:return: True if collection is ascending sorted
:raise: :py:class:`ValueError` if collection is not ascending sorted
Examples:
>>> __assert_sorted([0, 1, 2, 4])
True
>>> __assert_sorted([10, -1, 5])
Traceback (most recent call last):
...
ValueError: Collection must be ascending sorted
"""
if collection != sorted(collection):
raise ValueError("Collection must be ascending sorted")
return True
if __name__ == "__main__":
import sys
"""
user_input = input('Enter numbers separated by comma:\n').strip()
collection = [int(item) for item in user_input.split(',')]
try:
__assert_sorted(collection)
except ValueError:
sys.exit('Sequence must be ascending sorted to apply interpolation search')
target_input = input('Enter a single number to be found in the list:\n')
target = int(target_input)
"""
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")