這個遞歸二分法搜索算法可以更有效嗎？

我見過這種算法的很多不同的實現，但我想知道是否有辦法提高效率，而不僅僅是製作搜索二進制文件。我已經設計了算法的這個特定版本，因此，將立即檢查數組/列表的邊緣和中點以便搜索關鍵字，以避免在您尋找的關鍵字只是第一個，中間時循環搜索或最後一個元素。這個遞歸二分法搜索算法可以更有效嗎？

def searchRB(the_array, the_key, imin, imax): 
    print("searching") 
    found = False 
    if (0 > the_key or the_key > len(the_array)): 
     return found 
    else: 
     imid = imin + ((imax - imin) // 2) 
     if imid == the_key or imin == the_key or imax == the_key: 
      found = True 
      return found 
     elif the_array[imid] > the_key: 
      return searchRB(the_array, the_key, imin, imid-1) 
     elif the_array[imid] < the_key: 
      return searchRB(the_array, the_key, imid+1, imax) 
     else: 
      return found

例如，如果您正在尋找在1-100一個列表中的號碼1，這將找到它的第一個循環，不像其他一些實現。

但是，我不確定這是否實際上提高了效率（除了某些邊緣情況），並且如果在繼續循環時檢查list/array中的第一個，中間和最終值實際上是有害的並且每次都必須檢查這三個值。

這是這種算法的好壞實施，還是我只是分裂頭髮？

來源

2015-10-03 123

迭代二進制搜索將更有效。 – keshlam

有趣的是，你能否詳述一下爲什麼是這樣？ – 123

你將如何開始搜索？ the_key，imin，imax的值是什麼？ – LetzerWille

最大的問題是從遞歸方法改爲使用while循環，保存了調用堆棧（因爲python沒有尾遞歸）。

您可以優化的小冗餘。已經優化算法就夠了，不要over optimise除非你瞭解編譯器

如果你打算去樹左邊你會一遍又一遍比較相同愛民，然而這整條生產線可能會被並行化或依次

if the_array[imid] == the_key or the_array[min] == the_key or the_array[imax] == the_key:

做同樣，這可能與高速緩存性能一塌糊塗，你會有無the_array [分鐘]一直被保留在緩存中。有時候，編譯器會在你試圖訪問緩存的索引周圍存儲數組的塊。你可能會浪費更多的緩存，而不僅僅是那個1值。

也可以優化這樣的語句，只需鍵入return True即可，但編譯器應該再次選擇它。

found = True return found

不具有found作爲對象將優化代碼，因爲該對象將不被存儲在存儲器中的全部時間。

這else語句似乎是多餘的，因爲沒有可能的方式去說別人 else return found

實際相關的優化將來自更多地瞭解數據集。

如果您能夠預處理數據（或有更多關於數據的信息），您可以使用其他算法。

來源

2015-10-03 03:35:53

我在這裏注意到的一件事是，搜索與密鑰等效的最小值，最大值不能很好地工作。就像你說的那樣，我每次循環時都會比較相同的最小值和最大值（這是無用的），但是如果使用'the_key == the_array [imin]或the_key == the_array [imax]'，該指數超出範圍。我認爲最好完全放棄它，並且只將關鍵點與中點進行比較。 – 123

是剛剛比較中點，我也認爲你的邏輯什麼時候打破有點壞，它應該比較中間0和數組的長度，以確定索引是否在界限內 –

應該在函數的開頭，這個語句應該是'if 0> imid或者imid> len（the_array）：'就像你說的那樣。 – 123

這個遞歸二分法搜索算法可以更有效嗎？

回答

相關問題