有关算法设计手册的问题 - 字典的数据结构

Question

我开始阅读算法设计手册，在阅读它时遇到了我没有收到的一行。有人能澄清我作者在这里的含义吗？该生产线是：

排序链表或数组 - 维护有序链表通常 不值电子FF ORT，除非你想消除重复，因为我们 不能在这样的数据结构进行二进制搜索。当且仅当插入或删除的次数不多时，排序后的数组将会是合适的。

这一行是在选择字典数据结构的上下文中。 我没有得到的一点是，为什么作者说，“除非您试图消除重复，否则维护排序的链接通常不值得为之付出努力，，因为我们的 无法在这样的数据结构中执行二进制搜索”

从我的理解我google了看我们是否可以二进制搜索排序阵列和基于我发现它看起来我们可以。所以我不确定。

有人能帮我理解吗？

非常感谢。

Answer 1

您无法高效地在链接列表上执行二进制搜索，因为您不能在常量时间内随机搜索它。要找到中点，你必须做n/2步（遍历列表）。这增加了很大的开销，并使得列表不适用于二进制搜索数据结构。