在java中的有序列表中进行二进制搜索

Question

我正在寻找一种在java中实现代码的方法,其工作方式与在有序ArrayList中的二进制搜索相同,但对于有序列表谢谢

Answer 1

您可以使用

Collections.<T>binarySearch(List<T> list, T key)

用于任何二进制搜索List.它的工作原理上ArrayList和LinkedList和其他List.

然而:

如果您可以直接访问每个元素,则二进制搜索速度很快:

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

如果您List不提供"随机访问",您可以通过创建List提供此功能的副本来获得更好的运气.

LinkedList<String> list = new LinkedList<String>();
// fill

要么这样

ArrayList<String> fastList = new ArrayList<String>(list);
Collections.binarySearch(fastList, "Hello World");

或许是这样的

String[] array = list.toArray(new String[list.size()]);
Arrays.binarySearch(array, "Hello World");

如果List默认情况下没有订购,并且您必须在搜索之前对其进行排序,那么通过对数组执行此操作可能会获得最佳结果

Collections.sort(list);

创建一个临时数组,该数组已排序并用于重新创建列表,如果直接使用数组,则应该能够阻止该列表.

String[] array = list.toArray(new String[list.size()]);
Arrays.sort(array);
Arrays.binarySearch(array, "Hello World");

Answer 2

鉴于anArrayList和 a都是有序的，该算法对于 an 和 a 应该是相同的。List