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

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

Answer 1

对于ArrayList和List ，算法应该是相同的，因为它们都是有序的。

Answer 2

您可以使用

Collections.binarySearch(List list, T key)

用于任何List上的二进制搜索。 它适用于ArrayList和LinkedList以及任何其他List 。

然而：

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

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

如果您的List不提供“随机访问”，您可以通过创建提供此function的List副本来获得更好的运气。

 LinkedList list = new LinkedList(); // fill 

要么这样

 ArrayList fastList = new ArrayList(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 3

“二进制搜索”只有在列表中的元素（或某些指向元素的指针）按顺序组织在内存中时才有意义，因此如果知道您的搜索已经缩小到索引“低”和“高”，则可以向右跳到（低+高）/ 2的元素，而不必穿过所有其他元素。 这不适用于通用List，它可以是LinkedList。 对于类似的东西，你不能比从列表的前面开始并按顺序遍历所有元素做得更好。

Answer 4

您还应该记住，如果未订购列表，则无法进行二进制搜索。 这没有意义。 二进制搜索是O(log n)因为您可以在每个点忽略列表的一半，因为您知道它是有序的。 如果未对该列表进行排序，则您的搜索为O（n），并且您不能使用二进制。

您自己的二进制搜索实现应如下所示：

 int binary_search(int A[], int key, int imin, int imax) { // test if array is empty if (imax < imin) // set is empty, so return value showing not found return KEY_NOT_FOUND; else { // calculate midpoint to cut set in half int imid = midpoint(imin, imax); // three-way comparison if (A[imid] > key) // key is in lower subset return binary_search(A, key, imin, imid-1); else if (A[imid] < key) // key is in upper subset return binary_search(A, key, imid+1, imax); else // key has been found return imid; } } 

来源： 维基百科

如果要使用Java.util实现，请使用：

 java.util.Arrays.binarySearch(int[] a, int key) 

数组a当然应该排序。