Arrays.BinarySearch 没有保证吗？
https://docs.oracle.com/ javase/1.5.0/docs/api/java/util/Arrays.html
Sun 没有提及其二分搜索实现的任何复杂性。这是一个错误吗？我知道它应该是 O(logn)，但是当他们没有明确说明这一点时，这让我感到紧张。他们的一些算法是这样做的，比如 Arrays.sort。
你们中有人了解实际实施情况吗？我自己还没有机会下载源代码！我猜想这是一个微不足道的二分搜索，但 Sun 有时会调整算法以获得更好的性能。
https://docs.oracle.com/javase/1.5.0/docs/api/java/util/Arrays.html
Sun does not mention any complexity for their binary-search implemention. Is this a mistake? I know it should be O(logn), but it makes me nervous when they don't state this explicitly. They do for some of their algoritms, like Arrays.sort.
Does any of you have any knowledge of the actual implementation? I have not had the opportunity to download the source code yet myself! I guess its a trivial binary search, but Sun do sometimes tweak the algoritms for better performance.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
根据定义，二分搜索是 O(log n) （平均），猜测没有必要明确提及。
binary search is by definition O(log n) (on average) guess there's no need to mention it explicittly.
java.util.Array的实现很简单，没有优化的空间。您可以在
JAVA_HOME/src.zip中找到源代码。此类中的排序算法
是使用二分搜索所必需的，是一种优化的快速排序，可提供 n*log(n) 性能（在许多数据集上）。The implementation of
java.util.Arrayis 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).无论数组包含什么，
Arrays.sort都保证返回一个排序的数组。Arrays.binarySearch(...)（小写“b”顺便说一句）不能保证您的数组可能未排序。现在编辑我的答案：看看代码，显然不可能比 O(log n) 执行得更差。但当然不能保证您会找到正确的值。
Arrays.sortis guaranteed to return a sorted array, no matter what your array contains.Arrays.binarySearch(...)(lowercase 'b' btw) cannot guarantee anything seen that your array may be unsorted.Now editing my answer: looking at the code apparently it's not possible to perform worse than O(log n). But there's of course no guarantee that you'll have found the correct value.
您可以在 JDK 安装中自行找到实际实现的源代码，或者使用 Google 搜索。例如，搜索“java.util.Arrays.java.html”。
但我毫不怀疑，binarySearch 方法的复杂度是
O(logN)。如果不是他们，有人会注意到……在过去十年左右的时间里。You can find the source code of the actual implementation yourself in your JDK installation, or using a Google search. For example, search for "java.util.Arrays.java.html".
But I have no doubt that the binarySearch methods are
O(logN). If they weren't somebody would have noticed ... in the last 10 or so years.