- Notifications
You must be signed in to change notification settings - Fork 46.7k
/
Copy pathinterpolation_search.py
137 lines (118 loc) · 4.19 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
"""
This is pure Python implementation of interpolation search algorithm
"""
definterpolation_search(sorted_collection: list[int], item: int) ->int|None:
"""
Searches for an item in a sorted collection by interpolation search algorithm.
Args:
sorted_collection: sorted list of integers
item: item value to search
Returns:
int: The index of the found item, or None if the item is not found.
Examples:
>>> interpolation_search([1, 2, 3, 4, 5], 2)
1
>>> interpolation_search([1, 2, 3, 4, 5], 4)
3
>>> interpolation_search([1, 2, 3, 4, 5], 6) is None
True
>>> interpolation_search([], 1) is None
True
>>> interpolation_search([100], 100)
0
>>> interpolation_search([1, 2, 3, 4, 5], 0) is None
True
>>> interpolation_search([1, 2, 3, 4, 5], 7) is None
True
>>> interpolation_search([1, 2, 3, 4, 5], 2)
1
>>> interpolation_search([1, 2, 3, 4, 5], 0) is None
True
>>> interpolation_search([1, 2, 3, 4, 5], 7) is None
True
>>> interpolation_search([1, 2, 3, 4, 5], 2)
1
>>> interpolation_search([5, 5, 5, 5, 5], 3) is None
True
"""
left=0
right=len(sorted_collection) -1
whileleft<=right:
# avoid divided by 0 during interpolation
ifsorted_collection[left] ==sorted_collection[right]:
ifsorted_collection[left] ==item:
returnleft
returnNone
point=left+ ((item-sorted_collection[left]) * (right-left)) // (
sorted_collection[right] -sorted_collection[left]
)
# out of range check
ifpoint<0orpoint>=len(sorted_collection):
returnNone
current_item=sorted_collection[point]
ifcurrent_item==item:
returnpoint
ifpoint<left:
right=left
left=point
elifpoint>right:
left=right
right=point
elifitem<current_item:
right=point-1
else:
left=point+1
returnNone
definterpolation_search_by_recursion(
sorted_collection: list[int], item: int, left: int=0, right: int|None=None
) ->int|None:
"""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)
Args:
sorted_collection: some sorted collection with comparable items
item: item value to search
left: left index in collection
right: right index in collection
Returns:
index of item in collection or None if item is not present
Examples:
>>> interpolation_search_by_recursion([0, 5, 7, 10, 15], 0)
0
>>> interpolation_search_by_recursion([0, 5, 7, 10, 15], 15)
4
>>> interpolation_search_by_recursion([0, 5, 7, 10, 15], 5)
1
>>> interpolation_search_by_recursion([0, 5, 7, 10, 15], 100) is None
True
>>> interpolation_search_by_recursion([5, 5, 5, 5, 5], 3) is None
True
"""
ifrightisNone:
right=len(sorted_collection) -1
# avoid divided by 0 during interpolation
ifsorted_collection[left] ==sorted_collection[right]:
ifsorted_collection[left] ==item:
returnleft
returnNone
point=left+ ((item-sorted_collection[left]) * (right-left)) // (
sorted_collection[right] -sorted_collection[left]
)
# out of range check
ifpoint<0orpoint>=len(sorted_collection):
returnNone
ifsorted_collection[point] ==item:
returnpoint
ifpoint<left:
returninterpolation_search_by_recursion(sorted_collection, item, point, left)
ifpoint>right:
returninterpolation_search_by_recursion(sorted_collection, item, right, left)
ifsorted_collection[point] >item:
returninterpolation_search_by_recursion(
sorted_collection, item, left, point-1
)
returninterpolation_search_by_recursion(sorted_collection, item, point+1, right)
if__name__=="__main__":
importdoctest
doctest.testmod()
