我正在尝试编写一个递归函数,该函数返回单词在已排序单词列表中的位置,或者None
在找不到单词时返回。以下是代码:
def partition(t,kw,upper,lower):
if ((upper-lower) > 1):
pivot = lower + (upper-lower)//2
print("pivot is now {}".format(pivot))
if (kw >= t[pivot]):
lower = pivot
print("searching on the right",upper,lower)
return(partition(t,kw,upper,lower))
elif (kw <= t[pivot-1]):
upper = pivot-1
print("searching on the left",upper,lower)
return(partition(t,kw,upper,lower))
else:
return None
#that means the keyword is between t[pivot-1] and t[pivot]
#which means it doesnt exist in the list
if (upper - lower) <= 1:
if (kw == t[upper]):
print("found element {} at upper bound {}".format(kw,upper))
return(upper)
elif (kw == t[lower]):
print("found element {} at lower bound {}".format(kw,lower))
return(lower)
else:
return None
def search(t, kw):
u = len(t)
partition(t,kw,u,0)
如您所见,无论何时调用函数,我都返回了该函数(不返回是使用递归调用时的常见错误)。同时,这是我使用的示例数组:
['', '', '150', '150', '1997,with', '36', '49', 'An', 'Annotated', 'Annotation', 'Bibliography', 'China', 'Chinese', 'Chinese', 'Classical', 'During', 'Dynasty', 'Hong', 'Hong', 'Hong', 'Hong', 'Hong', 'In', 'It', 'Kong', 'Kong', 'Kong', 'Kong,', 'Kong.', 'Mainland', 'Poets', 'Qing', 'They', 'Together,', 'Writings', 'a', 'a', 'a', 'a', 'a', 'active', 'activity,', 'addition', 'almost', 'and', 'and', 'and', 'and', 'and', 'and', 'annotations', 'anthologies', 'basic', 'been', 'before.', 'bibliographic', 'bibliographies,', 'by', 'carry', 'ci-poetry', 'ci-poetry', 'classical', 'collected', 'commentaries', 'compilation,', 'compilations', 'compiled', 'covered,', 'development', 'events', 'focused', 'form', 'form', 'formation,', 'from', 'from', 'has', 'help', 'hidden', 'in', 'in', 'in', 'in', 'includes', 'individual', 'information', 'information', 'introduces', 'invaluable', 'is', 'late', 'literary', 'literati', 'literature', 'literature.', 'membership,', 'most', 'never', 'not', 'of', 'of', 'of', 'of', 'of', 'of', 'of', 'of', 'of', 'of', 'offer', 'on', 'on', 'on', 'on', 'order', 'over', 'past', 'periods', 'pioneer', 'pity', 'poetic', 'poetry', 'poetry', 'poetry', 'poet’s', 'political', 'previous', 'previously', 'published', 'refuge', 'research', 'sequel', 'shi-', 'shi-', 'societies', 'societies', 'societies', 'societies.', 'societies.', 'splendor,', 'that', 'that', 'the', 'the', 'the', 'the', 'the', 'the', 'the', 'the', 'the', 'the', 'the', 'the', 'these', 'these', 'these', 'this', 'times', 'to', 'to', 'to', 'to', 'to', 'to', 'took', 'tools', 'topic', 'tradition.', 'turmoil', 'two', 'uncover', 'understand', 'understanding', 'unique', 'up', 'various', 'very', 'volume,', 'which', 'works,', 'worthwhile', 'would', 'years,']
我正在搜索该词"Qing"
,该词应排在第31位。现在看来该函数可以找到我需要的单词,但无法返回:
the result is
pivot is now 92
searching on the left 91 0
pivot is now 45
searching on the left 44 0
pivot is now 22
searching on the right 44 22
pivot is now 33
searching on the left 32 22
pivot is now 27
searching on the right 32 27
pivot is now 29
searching on the right 32 29
pivot is now 30
searching on the right 32 30
pivot is now 31
searching on the right 32 31
found element Qing at lower bound 31
None
我尝试搜索与递归函数有关的问题,但似乎没有太多相关的内容。SO上的大多数帖子都是由于未返回递归函数引起的,我真的不确定这里出了什么问题。
您的功能似乎正在运行。我认为您只是忘记了从搜索中返回,即
def search(t, kw):
u = len(t)
lower = partition(t,kw,u,0)
return lower
产出
...
searching on the right 32 30
pivot is now 31
searching on the right 32 31
found element Qing at lower bound 31
31
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句