8 java algorithm list binary-search data-structures
我不确定为什么List作为一般数据结构应该具有二进制搜索算法,因为列表是排序的.get接受索引的方法是否顺序遍历List,至少对于List's子类型LinkedList？如果是这样,我认为使用binarySearch与顺序比较相比没有任何优势LinkedList.当然,除非我们限制List,否则我们ArrayList可以更自信地进行binarySearch.
我的理解是否正确？谢谢.
tem*_*def 13
有很多方法可以实现List.有ArrayList,LinkedList,CopyOnWriteArrayList,等在标准的Java库和超出(其他实现主机VLists,循环缓冲器,歪斜二项式列表,可扩展阵列,2-3手指树木等).提供二进制搜索背后的想法是,虽然并非所有List实现都支持随机访问,但是那些可以从二进制搜索的通用实现中获益的那些可以使每个数据结构的作者不必从头重新实现它.例如,如果我实现一个支持随机访问的疯狂新列表结构,如果我实现List接口,我可以自动从Collections类获得二进制搜索.
有趣的binarySearch是,编写该方法使得它查看类型List并查看它是否RandomAccess在实际执行二进制搜索之前实现了接口.如果列表没有实现RandomAccess,则该方法使用带有迭代器的修改二进制搜索,而不是使用标准二进制搜索,该迭代器保证最多进行O(n)次迭代和O(log n)次比较.我们的想法是跟踪最后一个探测器落在哪里,然后向前或向后走适当数量的步骤以找到下一个探测位置等.完成的总工作量最多为n/2 + n/4 + n/8 + n/16 + ... = 2n,所以在最坏的情况下,它只是最坏情况线性搜索的两倍.
简而言之,提供通用实现binarySearch并不总是能够快速搜索List以获取某些内容,但对于支持快速访问的结构,它可以产生巨大的差异并节省大量的实现时间.此外,对在O(n)时间内运行的修改后的二进制搜索进行优雅降级意味着实现不会比标准线性扫描更糟糕.
这种推理类似于C++算法设计背后的原因,C++算法在通用值范围内运行.这些算法的效率可能比基于每个数据结构的算法的特定版本差得多,但是具有通用版本可用意味着任何支持迭代器的新容器都可以自动拥有许多功能,而不仅仅是在界面中指定.
希望这可以帮助!