線性搜索或二進制搜索或二叉搜索樹

如果我知道，在列表中搜索元素，比如包含順序排序32個元素，首先是四個位置中出現，

這是最好的搜索算法。

線性搜索至少需要4次迭代.... 二進制搜索至少5次迭代如何二叉搜索樹..沒有給出更好的解決方案在這種情況下或等於二分查找...

我相信線性搜索會更適合這種情況..

有人可以證實這一點嗎？

2011-10-05 user976027

如果您知道位置在前4個位置，而線性搜索更好，因爲您必須測試不超過4個元素。使用二進制搜索lg 32 = 5，所以你將不得不測試最多5個元素。

此外，對於少量這樣的元素，時間差異可以忽略不計，您可以通過保持簡單並進行線性搜索來獲得最佳服務。

對於O（1）時間，您可能也可以使用HashTable或HashSet，但對於少量數據，線性搜索可能會比執行散列函數更快。

如果這個小的差別確實很重要，我會建議在它運行的環境中測量它。

2011-10-05 06:20:18 spatulamania

什麼關於二叉搜索樹？它與二分查找相似嗎？ – user976027

是的，二叉搜索樹是圍繞二進制搜索進行設計的數據結構。一個二叉搜索樹比一個已排序數組的優點是插入和刪除元素。查找時間（給定樹是平衡的）是相同的。 – spatulamania

你可以對前4個元素進行二分搜索。它將是lg 4 = 2次迭代！ :-)

2011-10-05 06:23:28 Aliza

謝謝你..搜索必須做的所有元素..只有少數我會知道它將在前4個元素 – user976027

有了這麼多的元素和具體的應用程序，二叉搜索樹會是一個矯枉過正的問題。

此外，爲了解決目前的問題，線性搜索會更好，因爲定位特定元素的預期迭代次數將超過二進制搜索。

對於現實生活場景，這樣呈現的問題將非常罕見。因此，在排序的數組上使用二進制搜索總是更好。

2011-10-05 06:24:22

如果數據以某種方式均勻分佈，則使用插值搜索是明智的。通過使用分配知識，您有一個很好的機會在一個步驟中猜測正確的位置。預期的複雜度是O（log（log（n）））。

這裏是我的網頁，在那裏我有在Java中實現的算法鏈接：Algoritmy.net - interpolation search implementation

2011-10-05 20:11:31 malejpavouk

回答