indexOf 还是二分搜索? [英] indexOf or Binary Search?

问题描述

我有一个字符串数组列表，字符串按顺序排列，我想找到特定元素的索引，哪个会更快?

1. 执行列表的 indexOf()
2. 在等效数组中执行二分查找?

解决方案

您可以直接使用 Collections.binarySearch 以提高效率:

public static int binarySearch(List<? extends Comparable<? super T>> list,T键)

<块引用>

使用二进制搜索指定对象的指定列表搜索算法.列表必须按升序排序根据其元素的自然顺序(如sort(List) 方法)之前进行此调用.如果没有排序，则结果未定义.如果列表包含多个元素等于指定的对象，不保证会找到哪个.

此方法在 log(n) 时间内运行，用于随机访问"列表(其中提供近乎恒定的时间定位访问).如果指定列表没有实现 RandomAccess 接口并且很大，这方法将执行基于迭代器的二进制搜索，执行 O(n) 链接遍历和 O(log n) 元素比较.

虽然 List.indexOf 在 O(n) 时间内运行，但并不关心 List 是否已排序.

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?

1. Performing indexOf() of lists
2. Performing a binary search in an equivalent array?

解决方案

You can use Collections.binarySearch directly for better efficience:

public static <T> int binarySearch(List<? extends Comparable<? super T>> list,
                   T key)

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.

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.

While List.indexOf runs in O(n) time, doesn't care about if the List is sorted or not.

这篇关于indexOf 还是二分搜索?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！