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

Question

我有一个搜索键列表（'l'）的函数搜索，如果找到则返回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

对于您的基本情况，您只是在索引0找到该项目，对不对？返回0.

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

对于你的递归部分，让我们考虑一下返回的内容。假设该项目在索引5处。因为我们已经通过递归调用了一个被移动了一个元素的列表，所以它会找到它并返回4.（4，而不是5.您是否明白为什么？）

在我们返回之前，我们需要添加一个来解除索引。

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

Answer 2

问题是，您正在切片清单的尾部，而不保留有关切片发生位置的任何信息。

事实上，根本不需要切分列表，因为您只需在列表中进行索引查找即可。

线性搜索的算法是原始递归，所以如果你能想出一个迭代解决方案，递归解决方案是平凡可及的（反之亦然）。

所以迭代的解决方案可能是这个样子：

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 3

您需要对索引进行跟踪。因为你的最终返回值[如果真正的搜索发生]是布尔值，所以你必须改变它。
我想类似下面的代码应该帮助你，但不要对其进行全面测试，因为我只是想跨意图获取，也没有彻底的测试逻辑 -

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 4

你的API的设计是严重有缺陷的。

>>> False == 0 
True 

你的导师正在为你设置惊喜。例如：

where = search(["non-foo", "not-foo"], "foo") # returns False 
if where == 0: 
    print "foo is in pole position" 
    # but "foo" isn't even a candidate 

使其在失败时返回None。试试这个：

>>> def search(alist, key, pos=None): 
...  if pos is None: pos = len(alist) - 1 
...  if pos < 0: return None 
...  if key == alist[pos]: return pos 
...  return search(alist, key, pos - 1) 
... 
>>> search([1,2,3], 4) # -> None 
>>> search([1,2,3], 3) 
2 
>>> search([1,2,3], 2) 
1 
>>> search([1,2,3], 1) 
0 
>>> search([], 1) # -> None 
>>> 

此方法的其他功能：（1）向您介绍它可以用在一个局部变量会在非递归函数中使用的“隐藏” ARGS的概念。 （2）避免所有字符串切片的成本。

=========================================

对于这里@ inspectorG4dget的利益，是我@安文的回答重构：

def xsearch(l,key,idx=0): 
    if l: # checks if list exists 
     if l[0] == key:  # base case - first index is key 
      return idx 
     s = xsearch(l[1:], key, (idx + 1))  # recursion 
     if s is not False:   
      return s 
     #### and if s is False, it falls through and returns False #### 
     #### so it can return s unconditionally!     #### 
    return False   # returns false if key not found 

def ysearch(l,key,idx=0): 
    if l: # checks if list exists 
     if l[0] == key:  # base case - first index is key 
      return idx 
     return ysearch(l[1:], key, (idx + 1))  # recursion 
    return False   # returns false if key not found 
    #### above statement is better put closer to the `if` #### 

def zsearch(l,key,idx=0): 
    if not l: # checks if list exists 
     return False 
    if l[0] == key:  # base case - first index is key 
     return idx 
    return zsearch(l[1:], key, (idx + 1))  # recursion