二進制搜索O（log2（n））更改基址

Question

在二分查找中，我知道它的複雜性以log2（n）運行。搜索利用列表被排序的事實，所以我們可以假設數組中的每個項目都有一個'標記'（它的索引）作爲附加信息來減少運行時間。有什麼方法可以添加額外的「標籤」來進一步降低其複雜性？用不同的話來說，我們可以實現更高級別的組織結構嗎？

Answer 1

如果您的搜索算法基於比較，並且列表已排序，則log2（n）是下限。但是，有一些時空折衷算法或數據結構也可以用於搜索。最常見的是HashTable。

Answer 2

我不知道這是否適用於您的案例，但是如果您正在處理簡單的關聯邏輯（即，您沒有鍵/值區分，只有鍵），並且您的客戶已經擁有訪問密鑰，只是試圖找出一個元素是否屬於容器，然後有一個非常簡單和快速的解決方案，在尋找數據結構來完成這項工作時，往往沒有多少解決方案。

只需將一個或多個後向指針（或取決於語言的反向引用）存儲到密鑰內的容器即可。現在您不再搜索容器以查看密鑰是否屬於它。您可以搜索密鑰本身，在它的後端指示器中查看密鑰是否屬於容器。

即使您的密鑰一次不屬於太多容器，這通常也會超過最快的哈希表實現。如果它們一次只屬於一個容器，那麼只需查看背面指針是否指向您感興趣的容器即可進行快速定時檢查。

這是一個比容器更侵入式的解決方案這與您的關鍵表示完全分離，但如果您的需求符合標準，則難以超過設定邏輯的速度（查找某個屬性是否屬於某個集合，找到集合交集，聯合，差異）：即，您正在處理簡單的關聯邏輯和你的密鑰一次不屬於太多這樣的聚集。