Python中的递归函数来搜索列表中的项目
我正在尝试/需要编写一个递归函数，如果元素在排序列表中，则返回 True/False 值。我被要求不要使用“in”关键字来获得答案。我的代码如下，我想我很接近，但我似乎无法让函数返回正确的值：
def listSplitter(listToProcess, numToFind):
lenOfList = len(listToProcess)
if lenOfList == 1:
if numToFind == listToProcess[0]:
return True
else:
return False
else:
if lenOfList % 2 == 0:
list1 = listToProcess[0:int(lenOfList / 2)]
list2 = listToProcess[int(lenOfList / 2):int(lenOfList)]
if list1[-1] >= numToFind and list1[0] <= numToFind:
return (list1, numToFind)
#return
elif list2[-1] >= numToFind and list2[0] <= numToFind:
return listSplitter(list2, numToFind)
#return
else:
list1 = listToProcess[0:int(lenOfList / 2)]
list2 = listToProcess[int(lenOfList / 2):int(lenOfList)]
if list1[-1] >= numToFind and list1[0] <= numToFind:
return listSplitter(list1, numToFind)
#return
elif list2[-1] <= numToFind and list1[0] >= numToFind:
return listSplitter(list2, numToFind)
#return
def ordered_contains(S, x):
return listSplitter(S,x)
#result = listSplitter(S, x)
#return result
A = [2, 16, 26, 32, 52, 71, 80, 88]
print("A contains 32: {}".format(ordered_contains(A, 32)))
print("A contains 7: {}".format(ordered_contains(A, 7)))
print("A contains -10: {}".format(ordered_contains(A, -10)))
print("n(Did those results match the earlier example?)")
这是输出：
A contains 32: ([2, 16, 26, 32], 32)
A contains 7: ([2, 16, 26, 32], 7)
A contains -10: None
(Did those results match the earlier example?)
我错过了什么？
任何帮助将不胜感激。
谢谢
回答
您的代码中存在一些问题：
- 错别字：
- 第 16 行：
return (list1, numToFind)->return listSplitter(list1, numToFind) - 第 28 行：
elif list2[-1] <= numToFind and list1[0] >= numToFind:->elif list2[-1] >= numToFind and list2[0] <= numToFind:（如果这不是打字错误，那么我认为它在逻辑上是不正确的）
- 第 16 行：
- 如果您更正上面错别字，你会看到，在2例码
if lenOfList% 2 == 0:和else是相同的。因此，没有必要将这两种情况分开。 - 的逻辑
list1 = listToProcess[0:int(lenOfList / 2)] list2 = listToProcess[int(lenOfList / 2):int(lenOfList)] if list1[-1] >= numToFind and list1[0] <= numToFind: return listSplitter(list1, numToFind) elif list2[-1] >= numToFind and list2[0] <= numToFind: return listSplitter(list2, numToFind)将错过一种情况，其中
list1和list2具有 1 个元素并且它们都不同于numToFind. 这就是为什么None在某些情况下会返回的原因。要处理这种情况，只需return False在上面的代码末尾添加。
这是我纠正上述问题后的代码：
def listSplitter(listToProcess, numToFind):
lenOfList = len(listToProcess)
if lenOfList == 1:
return numToFind == listToProcess[0]
list1 = listToProcess[0:int(lenOfList / 2)]
list2 = listToProcess[int(lenOfList / 2):int(lenOfList)]
if list1[-1] >= numToFind and list1[0] <= numToFind:
return listSplitter(list1, numToFind)
elif list2[-1] >= numToFind and list2[0] <= numToFind:
return listSplitter(list2, numToFind)
return False
def ordered_contains(S, x):
return listSplitter(S,x)
A = [2, 16, 26, 32, 52, 71, 80, 88]
print("A contains 32: {}".format(ordered_contains(A, 32)))
print("A contains 7: {}".format(ordered_contains(A, 7)))
print("A contains -10: {}".format(ordered_contains(A, -10)))
print("n(Did those results match the earlier example?)")
输出：
A contains 32: True
A contains 7: False
A contains -10: False
(Did those results match the earlier example?)