Python中的递归函数来搜索列表中的项目

Question

我正在尝试/需要编写一个递归函数，如果元素在排序列表中，则返回 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?)

我错过了什么？

任何帮助将不胜感激。

谢谢

Answer 1

您的代码中存在一些问题：

1. 错别字：
   • 第 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:（如果这不是打字错误，那么我认为它在逻辑上是不正确的）
2. 如果您更正上面错别字，你会看到，在2例码if lenOfList% 2 == 0:和else是相同的。因此，没有必要将这两种情况分开。
3. 的逻辑

   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?)