最近，我在链表上遇到了一个有趣的问题。给出了排序的单链接列表，我们必须从该列表中搜索一个元素。
时间复杂度不应超过O(log n)。看来我们需要在此链接列表上应用二进制搜索。怎么样？由于如果我们尝试应用二进制搜索算法，则链表不会提供随机访问权限，因此链表将达到O（n），因为我们需要查找列表的长度并转到中间。
O(log n)
有任何想法吗？
普通的单链接列表当然是不可能的。
素描证明：以检查单链表的最后一个节点，我们必须执行n-1操作的事实之后的“下一个”指针[证明是用归纳的，世界上只有一个参照k+1个节点，是在k日节点，并且需要执行以下操作]。对于某些输入，有必要检查最后一个节点（特别是，如果搜索到的元素等于或大于其值）。因此，对于某些输入，所需时间与成正比n。
n-1
k+1
k
n
您要么需要更多时间，要么需要不同的数据结构。
请注意，您可以使用二进制搜索在O（log n） 比较中 执行此操作。这将花费更多的 时间 ，因此，只有在比较比列表遍历昂贵得多的情况下，此事实才有意义。
