indexOf还是二进制搜索? [英] indexOf or Binary Search?
问题描述
我有一个字符串数组列表，该字符串按排序顺序排列，我想查找特定元素的索引，哪一个会更快?
I have an array list of strings, the string are in sorted order, i want to find the index of a particular element, Which one will be faster?
- 执行列表的indexOf()
- 在等效数组中执行二进制搜索?
推荐答案
您可以直接使用Collections.binarySearch以获得更高的效率:
You can use Collections.binarySearch directly for better efficience:
public static <T> int binarySearch(List<? extends Comparable<? super T>> list,
T key)
使用二进制文件在指定列表中搜索指定对象 搜索算法.该列表必须按升序排序 根据其元素的自然顺序(例如 在进行此调用之前，请先执行sort(List)方法).如果未排序，则 结果不确定.如果列表包含多个等于 指定的对象，不能保证会找到哪个对象.
Searches the specified list for the specified object using the binary search algorithm. The list must be sorted into ascending order according to the natural ordering of its elements (as by the sort(List) method) prior to making this call. If it is not sorted, the results are undefined. If the list contains multiple elements equal to the specified object, there is no guarantee which one will be found.
此方法以log(n)时间运行以获取随机访问"列表(其中 提供接近恒定时间的位置访问).如果指定清单 没有实现RandomAccess接口并且很大，这 方法将执行基于迭代器的二进制搜索，该搜索执行O(n)链接 遍历和O(log n)元素比较.
This method 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.
List.indexOf运行时间为O(n)，但不关心列表是否已排序.
While List.indexOf runs in O(n) time, doesn't care about if the List is sorted or not.
这篇关于indexOf还是二进制搜索?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
