Java 对大型抽象列表进行二进制搜索

Question

简短版本：

我有 LinkedList 的 n 随机 Integer 升序排列。
如果我在该列表上使用 Collections.binarySearch，它对我尝试过的任何 n 都可以正常工作。
但是，当我用 AbstractList 包装 LinkedList 时，对于 n>10000，二进制搜索开始表现得很奇怪。
它不是 运行 正确的二进制搜索，而是遍历整个列表。

---

长版：

我有一个 "file"，其中包含按升序排列的随机数，其中每行包含一个数字。
我想二进制搜索 "file" 并找到给定数字的索引（或 "line number"）。

一个简单的解决方案是读取整个文件并将每个数字放在 LinkedList 中，然后在 LinkedList.

上使用 Collections.binarySearch

现在，假设我得到的信息是从 "file" 中读取一行是一项代价高昂的操作。

为了尽量减少我必须阅读 "file" 的次数，我尝试做的是“模拟”LinkedList，并在每次我使用 AbstractList在 AbstractList 中使用 get(int index) 我刚刚从 "file".

中读取了行 index

当我的 AbstractList 大小为 <1000 时，这似乎工作得很好，当我尝试更大的列表时，二进制搜索似乎停止工作，并且只是遍历所有 AbstractList（从第一个节点到最后一个节点）。

---

我似乎已将问题缩小到使用带二进制搜索的大型 AbstractList。 我不确定为什么会这样，希望得到一些帮助。

我已经包含了“长版”，以防有人能够提出其他解决方案。

谢谢！

Answer 1

Javadoc to the rescue:

[binarySearch] runs in log(n) time for a "random access" list (which provides near-constant-time positional access). If the specified list does not implement the RandomAccess interface and is large, this method will do an iterator-based binary search that performs O(n) link traversals and O(log n) element comparisons.

LinkedList 和 AbstractList 不执行 RandomAccess.