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

Question

我开始阅读 Algorithm Design Manual，在阅读时遇到了一行我没有理解的内容。有人可以澄清一下作者在这里的意思吗？该行是:

排序的链表或数组——维护一个排序的链表通常是除非你试图消除重复项，否则不值得付出努力，因为我们不能在这样的数据结构中执行二进制搜索。排序的数组将当且仅当插入或删除不多时才合适。

这一行与为字典选择数据结构有关。我没有明白的一点是，为什么作者说“维护一个排序的链表通常不值得付出努力，除非你试图消除重复项，因为我们无法在这样的数据结构中执行二进制搜索"

根据我的理解，我用谷歌搜索看我们是否可以对排序数组进行二分搜索，根据我的发现，我们似乎可以。所以我不确定。

有人能帮我理解一下吗？

非常感谢。

Answer 1

你不能有效地对链表执行二进制搜索，因为你不能在常数时间内随机搜索它。要找到中点，您必须执行 n/2 个步骤(遍历列表)。这会增加很大的开销，并使列表不适合二进制搜索数据结构。