递归线性搜索 - 返回列表索引

Question

我有一个叫做 search 的函数，它会在一个列表（'l'）里查找某个关键字。如果找到了，就返回 True；如果没找到，就返回 False。现在我想让它在找到关键字时返回这个关键字的位置（索引），而不是 True；如果没找到，就返回 False。不过我对该怎么写返回的内容有点困惑。以下是我的代码：

def search(l,key):
    """
    locates key in list l.  if present, returns location as an index; 
    else returns False.
    PRE: l is a list.
    POST: l is unchanged; returns i such that l[i] == key; False otherwise.
    """

    if l:   # checks if list exists
        if l[0] == key:     # base case - first index is key
            return True

        s = search(l[1:], key)      # recursion
        if s is not False:          
            return s

    return False            # returns false if key not found

任何帮助都非常感谢，谢谢。

Answer 1

问题在于，你在切割列表的尾部时，没有保留任何关于切割位置的信息。

其实，你根本不需要切割列表，因为你可以直接通过索引来查找列表中的元素。

线性搜索的算法是比较基础的递归算法，所以如果你能想出一个迭代的解决方案，那么递归的解决方案也很容易得到（反之亦然）。

所以，迭代的解决方案可能看起来像这样：

for every integer i between zero and length of list
    if the element at position i in the list is equal to the key
        return i
else
   return "I couldn't find it"

把迭代的解决方案转成递归的方案，基本上就是把循环变成一个函数调用，函数的参数就是下一次循环迭代的值。循环变量是 i 和正在搜索的列表。为了让你从这个练习中学习，我就先说到这里。

Answer 2

你需要记录一下索引的位置。因为你最后返回的值（如果找到了True）是布尔值，所以你得把这个改一下。
我想下面的代码应该能帮到你，但一定要仔细测试一下，因为我只是想表达这个意思，并没有彻底测试过逻辑 -

def search(l,key,idx=0):
"""
locates key in list l.  if present, returns location as an index; 
else returns False.
PRE: l is a list.
POST: l is unchanged; returns i such that l[i] == key; False otherwise.
"""

if l:   # checks if list exists
    if l[0] == key:     # base case - first index is key
    return idx

    s = search(l[1:], key, (idx + 1))      # recursion
    if s is not False:          
        return s

return False            # returns false if key not found

Answer 3

对于你的基本情况，你只需要找到索引为0的那个项目，对吧？返回0。

if l[0] == key:     # base case - first index is key
    return 0

接下来是递归的部分，我们来想想该返回什么。假设这个项目在索引5的位置。因为我们传递给递归调用的是一个向左移动了一个元素的列表，所以它会找到这个项目并返回4。（返回4，而不是5。你明白为什么吗？）

在返回之前，我们需要加1来调整索引。

s = search(l[1:], key)      # recursion
if s is not False:          
    return s + 1