java - 不能保证 Arrays.BinarySearch？

Question

https://docs.oracle.com/javase/1.5.0/docs/api/java/util/Arrays.html

Sun 没有提到他们的二进制搜索实现的任何复杂性。这是一个错误吗？我知道应该是这样O(logn)，但是当他们没有明确说明这一点时，我会感到紧张。他们为他们的一些算法做，比如 Arrays.sort。

你们中的任何人都对实际实施有任何了解吗？我自己还没有机会下载源代码！我想这是一个微不足道的二分搜索，但 Sun 有时会调整算法以获得更好的性能。

Answer 1

根据定义，二进制搜索是 O(log n) （平均而言）猜测没有必要明确提及它。

Answer 2

The implementation of java.util.Array is straightforward and there is no room for optimizations.

You find the source code in JAVA_HOME/src.zip. The sorting alogrithm in this class, which is required in order to use binary search, is a optimized quicksort wich offers n*log(n) performance (on many data sets).

Answer 3

Arrays.sort保证返回一个排序的数组，不管你的数组包含什么。

Arrays.binarySearch(...) （小写“b”顺便说一句）不能保证您的数组可能未排序。

现在编辑我的答案：查看代码显然不可能比 O(log n) 更差。但是当然不能保证你会找到正确的值。

Answer 4

你们中的任何人都对实际实施有任何了解吗？

您可以在自己的 JDK 安装中或使用 Google 搜索找到实际实现的源代码。例如，搜索“java.util.Arrays.java.html”。

但我毫不怀疑 binarySearch 方法是O(logN). 如果他们不是有人会注意到……在过去 10 年左右的时间里。