Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitb6c3fa8

Browse files
weixuanhupoyea
authored andcommitted
Interpolation search - fix endless loop bug, divide 0 bug and update description (TheAlgorithms#793)
* fix endless loop bug, divide 0 bug and update descriptionfix an endless bug, for example, if collection = [10,30,40,45,50,66,77,93], item = 67.fix divide 0 bug, when right=left it is not OK to point = left + ((item - sorted_collection[left]) * (right - left)) // (sorted_collection[right] - sorted_collection[left])update 'sorted' to 'ascending sorted' in description to avoid confusion* delete swap files* delete 'address' and add input validation
1 parentf3608ac commitb6c3fa8

File tree

3 files changed

+160
-24
lines changed

3 files changed

+160
-24
lines changed

‎searches/interpolation_search.py

Lines changed: 59 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -11,16 +11,23 @@
1111

1212
definterpolation_search(sorted_collection,item):
1313
"""Pure implementation of interpolation search algorithm in Python
14-
Be careful collection must be sorted, otherwise result will be
14+
Be careful collection must beascendingsorted, otherwise result will be
1515
unpredictable
16-
:param sorted_collection: some sorted collection with comparable items
16+
:param sorted_collection: someascendingsorted collection with comparable items
1717
:param item: item value to search
1818
:return: index of found item or None if item is not found
1919
"""
2020
left=0
2121
right=len(sorted_collection)-1
2222

2323
whileleft<=right:
24+
#avoid devided by 0 during interpolation
25+
ifsorted_collection[left]==sorted_collection[right]:
26+
ifsorted_collection[left]==item:
27+
returnleft
28+
else:
29+
returnNone
30+
2431
point=left+ ((item-sorted_collection[left])* (right-left))// (sorted_collection[right]-sorted_collection[left])
2532

2633
#out of range check
@@ -31,66 +38,97 @@ def interpolation_search(sorted_collection, item):
3138
ifcurrent_item==item:
3239
returnpoint
3340
else:
34-
ifitem<current_item:
35-
right=point-1
36-
else:
37-
left=point+1
41+
ifpoint<left:
42+
right=left
43+
left=point
44+
elifpoint>right:
45+
left=right
46+
right=point
47+
else:
48+
ifitem<current_item:
49+
right=point-1
50+
else:
51+
left=point+1
3852
returnNone
3953

40-
4154
definterpolation_search_by_recursion(sorted_collection,item,left,right):
4255

4356
"""Pure implementation of interpolation search algorithm in Python by recursion
44-
Be careful collection must be sorted, otherwise result will be
57+
Be careful collection must beascendingsorted, otherwise result will be
4558
unpredictable
4659
First recursion should be started with left=0 and right=(len(sorted_collection)-1)
47-
:param sorted_collection: some sorted collection with comparable items
60+
:param sorted_collection: someascendingsorted collection with comparable items
4861
:param item: item value to search
4962
:return: index of found item or None if item is not found
5063
"""
51-
point=left+ ((item-sorted_collection[left])* (right-left))// (sorted_collection[right]-sorted_collection[left])
5264

65+
#avoid devided by 0 during interpolation
66+
ifsorted_collection[left]==sorted_collection[right]:
67+
ifsorted_collection[left]==item:
68+
returnleft
69+
else:
70+
returnNone
71+
72+
point=left+ ((item-sorted_collection[left])* (right-left))// (sorted_collection[right]-sorted_collection[left])
73+
5374
#out of range check
5475
ifpoint<0orpoint>=len(sorted_collection):
5576
returnNone
5677

5778
ifsorted_collection[point]==item:
5879
returnpoint
59-
elifsorted_collection[point]>item:
60-
returninterpolation_search_by_recursion(sorted_collection,item,left,point-1)
80+
elifpoint<left:
81+
returninterpolation_search_by_recursion(sorted_collection,item,point,left)
82+
elifpoint>right:
83+
returninterpolation_search_by_recursion(sorted_collection,item,right,left)
6184
else:
62-
returninterpolation_search_by_recursion(sorted_collection,item,point+1,right)
85+
ifsorted_collection[point]>item:
86+
returninterpolation_search_by_recursion(sorted_collection,item,left,point-1)
87+
else:
88+
returninterpolation_search_by_recursion(sorted_collection,item,point+1,right)
6389

6490
def__assert_sorted(collection):
65-
"""Check if collection is sorted, if not - raises :py:class:`ValueError`
91+
"""Check if collection isascendingsorted, if not - raises :py:class:`ValueError`
6692
:param collection: collection
67-
:return: True if collection is sorted
68-
:raise: :py:class:`ValueError` if collection is not sorted
93+
:return: True if collection isascendingsorted
94+
:raise: :py:class:`ValueError` if collection is notascendingsorted
6995
Examples:
7096
>>> __assert_sorted([0, 1, 2, 4])
7197
True
7298
>>> __assert_sorted([10, -1, 5])
7399
Traceback (most recent call last):
74100
...
75-
ValueError: Collection must be sorted
101+
ValueError: Collection must beascendingsorted
76102
"""
77103
ifcollection!=sorted(collection):
78-
raiseValueError('Collection must be sorted')
104+
raiseValueError('Collection must beascendingsorted')
79105
returnTrue
80106

81107

82108
if__name__=='__main__':
83109
importsys
84-
85-
user_input=raw_input('Enter numbers separated by comma:\n').strip()
110+
111+
"""
112+
user_input = raw_input('Enter numbers separated by comma:\n').strip()
86113
collection = [int(item) for item in user_input.split(',')]
87114
try:
88115
__assert_sorted(collection)
89116
except ValueError:
90-
sys.exit('Sequence must be sorted to apply interpolation search')
117+
sys.exit('Sequence must beascendingsorted to apply interpolation search')
91118
92119
target_input = raw_input('Enter a single number to be found in the list:\n')
93120
target = int(target_input)
121+
"""
122+
123+
debug=0
124+
ifdebug==1:
125+
collection= [10,30,40,45,50,66,77,93]
126+
try:
127+
__assert_sorted(collection)
128+
exceptValueError:
129+
sys.exit('Sequence must be ascending sorted to apply interpolation search')
130+
target=67
131+
94132
result=interpolation_search(collection,target)
95133
ifresultisnotNone:
96134
print('{} found at positions: {}'.format(target,result))

‎searches/quick_select.py

Lines changed: 8 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -14,16 +14,21 @@ def _partition(data, pivot):
1414
"""
1515
less,equal,greater= [], [], []
1616
forelementindata:
17-
ifelement.address<pivot.address:
17+
ifelement<pivot:
1818
less.append(element)
19-
elifelement.address>pivot.address:
19+
elifelement>pivot:
2020
greater.append(element)
2121
else:
2222
equal.append(element)
2323
returnless,equal,greater
2424

2525
defquickSelect(list,k):
2626
#k = len(list) // 2 when trying to find the median (index that value would be when list is sorted)
27+
28+
#invalid input
29+
ifk>=len(list)ork<0:
30+
returnNone
31+
2732
smaller= []
2833
larger= []
2934
pivot=random.randint(0,len(list)-1)
@@ -41,4 +46,4 @@ def quickSelect(list, k):
4146
returnquickSelect(smaller,k)
4247
#must be in larger
4348
else:
44-
returnquickSelect(larger,k- (m+count))
49+
returnquickSelect(larger,k- (m+count))

‎searches/test_interpolation_search.py

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
importunittest
2+
frominterpolation_searchimportinterpolation_search,interpolation_search_by_recursion
3+
4+
classTest_interpolation_search(unittest.TestCase):
5+
defsetUp(self):
6+
# un-sorted case
7+
self.collection1= [5,3,4,6,7]
8+
self.item1=4
9+
# sorted case, result exists
10+
self.collection2= [10,30,40,45,50,66,77,93]
11+
self.item2=66
12+
# sorted case, result doesn't exist
13+
self.collection3= [10,30,40,45,50,66,77,93]
14+
self.item3=67
15+
# equal elements case, result exists
16+
self.collection4= [10,10,10,10,10]
17+
self.item4=10
18+
# equal elements case, result doesn't exist
19+
self.collection5= [10,10,10,10,10]
20+
self.item5=3
21+
# 1 element case, result exists
22+
self.collection6= [10]
23+
self.item6=10
24+
# 1 element case, result doesn't exists
25+
self.collection7= [10]
26+
self.item7=1
27+
28+
deftearDown(self):
29+
pass
30+
31+
deftest_interpolation_search(self):
32+
self.assertEqual(interpolation_search(self.collection1,self.item1),None)
33+
34+
self.assertEqual(interpolation_search(self.collection2,self.item2),self.collection2.index(self.item2))
35+
36+
self.assertEqual(interpolation_search(self.collection3,self.item3),None)
37+
38+
self.assertEqual(interpolation_search(self.collection4,self.item4),self.collection4.index(self.item4))
39+
40+
self.assertEqual(interpolation_search(self.collection5,self.item5),None)
41+
42+
self.assertEqual(interpolation_search(self.collection6,self.item6),self.collection6.index(self.item6))
43+
44+
self.assertEqual(interpolation_search(self.collection7,self.item7),None)
45+
46+
47+
48+
classTest_interpolation_search_by_recursion(unittest.TestCase):
49+
defsetUp(self):
50+
# un-sorted case
51+
self.collection1= [5,3,4,6,7]
52+
self.item1=4
53+
# sorted case, result exists
54+
self.collection2= [10,30,40,45,50,66,77,93]
55+
self.item2=66
56+
# sorted case, result doesn't exist
57+
self.collection3= [10,30,40,45,50,66,77,93]
58+
self.item3=67
59+
# equal elements case, result exists
60+
self.collection4= [10,10,10,10,10]
61+
self.item4=10
62+
# equal elements case, result doesn't exist
63+
self.collection5= [10,10,10,10,10]
64+
self.item5=3
65+
# 1 element case, result exists
66+
self.collection6= [10]
67+
self.item6=10
68+
# 1 element case, result doesn't exists
69+
self.collection7= [10]
70+
self.item7=1
71+
72+
deftearDown(self):
73+
pass
74+
75+
deftest_interpolation_search_by_recursion(self):
76+
self.assertEqual(interpolation_search_by_recursion(self.collection1,self.item1,0,len(self.collection1)-1),None)
77+
78+
self.assertEqual(interpolation_search_by_recursion(self.collection2,self.item2,0,len(self.collection2)-1),self.collection2.index(self.item2))
79+
80+
self.assertEqual(interpolation_search_by_recursion(self.collection3,self.item3,0,len(self.collection3)-1),None)
81+
82+
self.assertEqual(interpolation_search_by_recursion(self.collection4,self.item4,0,len(self.collection4)-1),self.collection4.index(self.item4))
83+
84+
self.assertEqual(interpolation_search_by_recursion(self.collection5,self.item5,0,len(self.collection5)-1),None)
85+
86+
self.assertEqual(interpolation_search_by_recursion(self.collection6,self.item6,0,len(self.collection6)-1),self.collection6.index(self.item6))
87+
88+
self.assertEqual(interpolation_search_by_recursion(self.collection7,self.item7,0,len(self.collection7)-1),None)
89+
90+
91+
92+
if__name__=='__main__':
93+
unittest.main()

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp