java - 为什么在 Java 中对列表进行 binarySearch？

Question

鉴于列表已排序，我不确定为什么作为通用数据结构的列表应该具有二进制搜索算法。接受索引的 get 方法不是按顺序遍历列表吗，至少对于 List 的子类型 LinkedList 是这样？如果是这样，与 LinkedList 的顺序比较相比，我看不出使用 binarySearch 有任何优势。当然，除非我们将 List 限制为 ArrayList，否则我们可以更有信心地进行 binarySearch。

我的理解对吗？谢谢。

Answer 1

有很多方法可以实现List。标准 Java 库中有 ArrayList、LinkedList、CopyOnWriteArrayList 等，除此之外还有许多其他实现(VLists，循环缓冲区、倾斜二项式列表、extendible arrays、2-3 finger trees 等)。提供二进制搜索背后的想法是，虽然并非所有 List 实现都支持随机访问，但那些支持随机访问的实现将受益于可用的二进制搜索的通用实现，这样每个数据结构的作者就不必从头开始重新实现它。例如，如果我实现了一个支持随机访问的疯狂新列表结构，如果我实现了 List 接口(interface)，我可以自动从 Collections 类中获得可用的二进制搜索。

有趣的是，binarySearch 方法是这样写的，它会查看 List 的类型，并查看它之前是否实现了 RandomAccess 接口(interface)它实际上进行了二进制搜索。如果列表未实现 RandomAccess，则该方法不会使用标准二分搜索，而是使用改进的二分搜索和迭代器，保证最多进行 O(n) 次迭代和 O(log n) 比较。这个想法是跟踪最后一个探测器着陆的位置，然后向前或向后走适当的步数以找到下一个探测器位置等。完成的总工作最多为 n/2 + n/4 + n/8 + n/16 + ... = 2n，所以在最坏的情况下，它只是最坏情况线性搜索的两倍。

简而言之，提供 binarySearch 的通用实现并不总能使快速搜索列表成为可能，但对于支持快速访问的结构，它可以产生巨大的差异，节省大量实现时间。此外，对在 O(n) 时间内运行的修改后的二分搜索进行优雅降级意味着该实现永远不会比标准线性扫描差太多。

这种推理类似于 C++ 算法设计背后的推理，后者对通用值范围进行操作。在每个数据结构的基础上，这些算法的效率可能比该算法的专用版本差得多，但是拥有可用的通用版本意味着任何支持迭代器的新容器都可以自动拥有许多可用的功能，而不仅仅是在接口(interface)中指定。

希望这对您有所帮助!