遞歸線性搜索 - 返回列表索引

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