algorithm - 找到未知尺寸列表的中间

Question

在最近的一次采访中，有人问我:

从第一个位置开始查找长度未知的已排序列表的中间元素。

我是这样回应的:

有 2 个位置计数器:

计数器1柜台2

将 counter1 增加 1，将 counter2 增加 2。当计数器 2 到达列表末尾时，计数器 1 将位于中间。我觉得这效率不高，因为我正在重新访问我已经看过的节点。无论哪种方式，是否有更高效的算法？

Answer 1

假设有一个链表，您可以在访问任意接近 N 个项目的同时做到这一点。

做 5/4 N:

• 遍历列表直到到达末尾，计算项目数。
• 在第 2 个元素的每个幂处放置一个 anchor 。跟踪最后 2 个 anchor 。
• 迭代之前的最后一个 anchor ，直到它到达列表的中间。

当您到达列表的末尾时，最后一个 anchor 位于中点之前，但至少已经到了一半。因此，完整迭代的 N + anchor 的最多 1/4 N = 5/4 N。

更频繁地丢弃 anchor ，例如在第 1.5^th 项的每个上限功率处，使您尽可能接近 N(以跟踪更多 anchor 为代价；但对于任何给定的 X 作为功率步长，渐近内存是常数)。