33"""
44
55
6- def interpolation_search (sorted_collection , item ):
7- """Pure implementation of interpolation search algorithm in Python
8- Be careful collection must be ascending sorted, otherwise result will be
9- unpredictable
10- :param sorted_collection: some ascending sorted collection with comparable items
11- :param item: item value to search
12- :return: index of found item or None if item is not found
6+ def interpolation_search (sorted_collection : list [int ], item : int ) -> int | None :
7+ """
8+ Searches for an item in a sorted collection by interpolation search algorithm.
9+
10+ Args:
11+ sorted_collection: sorted list of integers
12+ item: item value to search
13+
14+ Returns:
15+ int: The index of the found item, or None if the item is not found.
16+ Examples:
17+ >>> interpolation_search([1, 2, 3, 4, 5], 2)
18+ 1
19+ >>> interpolation_search([1, 2, 3, 4, 5], 4)
20+ 3
21+ >>> interpolation_search([1, 2, 3, 4, 5], 6) is None
22+ True
23+ >>> interpolation_search([], 1) is None
24+ True
25+ >>> interpolation_search([100], 100)
26+ 0
27+ >>> interpolation_search([1, 2, 3, 4, 5], 0) is None
28+ True
29+ >>> interpolation_search([1, 2, 3, 4, 5], 7) is None
30+ True
31+ >>> interpolation_search([1, 2, 3, 4, 5], 2)
32+ 1
33+ >>> interpolation_search([1, 2, 3, 4, 5], 0) is None
34+ True
35+ >>> interpolation_search([1, 2, 3, 4, 5], 7) is None
36+ True
37+ >>> interpolation_search([1, 2, 3, 4, 5], 2)
38+ 1
39+ >>> interpolation_search([5, 5, 5, 5, 5], 3) is None
40+ True
1341 """
1442 left = 0
1543 right = len (sorted_collection ) - 1
@@ -19,8 +47,7 @@ def interpolation_search(sorted_collection, item):
1947 if sorted_collection [left ] == sorted_collection [right ]:
2048 if sorted_collection [left ] == item :
2149 return left
22- else :
23- return None
50+ return None
2451
2552 point = left + ((item - sorted_collection [left ]) * (right - left )) // (
2653 sorted_collection [right ] - sorted_collection [left ]
@@ -33,7 +60,7 @@ def interpolation_search(sorted_collection, item):
3360 current_item = sorted_collection [point ]
3461 if current_item == item :
3562 return point
36- elif point < left :
63+ if point < left :
3764 right = left
3865 left = point
3966 elif point > right :
@@ -46,22 +73,42 @@ def interpolation_search(sorted_collection, item):
4673 return None
4774
4875
49- def interpolation_search_by_recursion (sorted_collection , item , left , right ):
76+ def interpolation_search_by_recursion (
77+ sorted_collection : list [int ], item : int , left : int = 0 , right : int | None = None
78+ ) -> int | None :
5079 """Pure implementation of interpolation search algorithm in Python by recursion
5180 Be careful collection must be ascending sorted, otherwise result will be
5281 unpredictable
5382 First recursion should be started with left=0 and right=(len(sorted_collection)-1)
54- :param sorted_collection: some ascending sorted collection with comparable items
55- :param item: item value to search
56- :return: index of found item or None if item is not found
57- """
5883
84+ Args:
85+ sorted_collection: some sorted collection with comparable items
86+ item: item value to search
87+ left: left index in collection
88+ right: right index in collection
89+
90+ Returns:
91+ index of item in collection or None if item is not present
92+
93+ Examples:
94+ >>> interpolation_search_by_recursion([0, 5, 7, 10, 15], 0)
95+ 0
96+ >>> interpolation_search_by_recursion([0, 5, 7, 10, 15], 15)
97+ 4
98+ >>> interpolation_search_by_recursion([0, 5, 7, 10, 15], 5)
99+ 1
100+ >>> interpolation_search_by_recursion([0, 5, 7, 10, 15], 100) is None
101+ True
102+ >>> interpolation_search_by_recursion([5, 5, 5, 5, 5], 3) is None
103+ True
104+ """
105+ if right is None :
106+ right = len (sorted_collection ) - 1
59107 # avoid divided by 0 during interpolation
60108 if sorted_collection [left ] == sorted_collection [right ]:
61109 if sorted_collection [left ] == item :
62110 return left
63- else :
64- return None
111+ return None
65112
66113 point = left + ((item - sorted_collection [left ]) * (right - left )) // (
67114 sorted_collection [right ] - sorted_collection [left ]
@@ -73,64 +120,18 @@ def interpolation_search_by_recursion(sorted_collection, item, left, right):
73120
74121 if sorted_collection [point ] == item :
75122 return point
76- elif point < left :
123+ if point < left :
77124 return interpolation_search_by_recursion (sorted_collection , item , point , left )
78- elif point > right :
125+ if point > right :
79126 return interpolation_search_by_recursion (sorted_collection , item , right , left )
80- elif sorted_collection [point ] > item :
127+ if sorted_collection [point ] > item :
81128 return interpolation_search_by_recursion (
82129 sorted_collection , item , left , point - 1
83130 )
84- else :
85- return interpolation_search_by_recursion (
86- sorted_collection , item , point + 1 , right
87- )
88-
89-
90- def __assert_sorted (collection ):
91- """Check if collection is ascending sorted, if not - raises :py:class:`ValueError`
92- :param collection: collection
93- :return: True if collection is ascending sorted
94- :raise: :py:class:`ValueError` if collection is not ascending sorted
95- Examples:
96- >>> __assert_sorted([0, 1, 2, 4])
97- True
98- >>> __assert_sorted([10, -1, 5])
99- Traceback (most recent call last):
100- ...
101- ValueError: Collection must be ascending sorted
102- """
103- if collection != sorted (collection ):
104- raise ValueError ("Collection must be ascending sorted" )
105- return True
131+ return interpolation_search_by_recursion (sorted_collection , item , point + 1 , right )
106132
107133
108134if __name__ == "__main__" :
109- import sys
135+ import doctest
110136
111- """
112- user_input = input('Enter numbers separated by comma:\n ').strip()
113- collection = [int(item) for item in user_input.split(',')]
114- try:
115- __assert_sorted(collection)
116- except ValueError:
117- sys.exit('Sequence must be ascending sorted to apply interpolation search')
118-
119- target_input = input('Enter a single number to be found in the list:\n ')
120- target = int(target_input)
121- """
122-
123- debug = 0
124- if debug == 1 :
125- collection = [10 , 30 , 40 , 45 , 50 , 66 , 77 , 93 ]
126- try :
127- __assert_sorted (collection )
128- except ValueError :
129- sys .exit ("Sequence must be ascending sorted to apply interpolation search" )
130- target = 67
131-
132- result = interpolation_search (collection , target )
133- if result is not None :
134- print (f"{ target } { result } )
135- else :
136- print ("Not found" )
137+ doctest .testmod ()
0 commit comments