8

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

4

4 回答 4

23

您可以使用

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

对于任何List. 它适用ArrayListLinkedList任何其他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");
于 2013-08-07T18:38:28.973 回答
1

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

于 2013-08-07T18:13:55.177 回答
1

“二分查找”仅在列表的元素(或某种指向元素的指针)在内存中按顺序组织时才有意义,因此如果知道您的搜索已缩小到索引 Low 和 High,您可以向右跳转到 (Low + High) / 2 处的元素,而不必经过所有其他元素。这不适用于一般列表,它可能是 LinkedList。对于这样的事情,你真的不能比从列表的前面开始并按顺序遍历所有元素做得更好。

于 2013-08-07T18:15:32.287 回答
-1

您还应该记住,如果列表未排序,则无法进行二进制搜索。这没有意义。二进制搜索是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当然应该排序。

于 2013-08-07T18:14:57.733 回答