有關算法設計手冊的問題 - 字典的數據結構

Question

我開始閱讀算法設計手冊，在閱讀它時遇到了我沒有收到的一行。有人能澄清我作者在這裏的含義嗎？該生產線是：

排序鏈表或數組 - 維護有序鏈表通常 不值電子FF ORT，除非你想消除重複，因爲我們 不能在這樣的數據結構進行二進制搜索。當且僅當插入或刪除的次數不多時，排序後的數組將會是合適的。

這一行是在選擇字典數據結構的上下文中。 我沒有得到的一點是，爲什麼作者說，「除非您試圖消除重複，否則維護排序的鏈接通常不值得爲之付出努力，，因爲我們的 無法在這樣的數據結構中執行二進制搜索」

從我的理解我google了看我們是否可以二進制搜索排序陣列和基於我發現它看起來我們可以。所以我不確定。

有人能幫我理解嗎？

非常感謝。

Answer 1

您無法高效地在鏈接列表上執行二進制搜索，因爲您不能在常量時間內隨機搜索它。要找到中點，你必須做n/2步（遍歷列表）。這增加了很大的開銷，並使得列表不適用於二進制搜索數據結構。