java - Arrays.BinarySearch 没有保证吗?

标签 java complexity-theory binary-search

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

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

你们中有人了解实际的实现情况吗?我自己还没有机会下载源代码!我猜想这是一个微不足道的二分搜索,但 Sun 有时会调整算法以获得更好的性能。

最佳答案

二分搜索根据定义是 O(log n)(平均),猜测没有必要明确提及。

关于java - Arrays.BinarySearch 没有保证吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2211947/

相关文章:

java - 将字符串转换为 JInternalFrame

centos - 无法使用 yum 或 rpm 在 Fedora 上安装 jdk

java - java.util.HashMap 类的 keySet() 方法的时间复杂度是多少?

两种递归方法的Java复杂度

algorithm - 在 0-1 数组中查找所有 1 为 “on the left” 的 1 的个数?

java - DB 列上的 Spring JPA 错误返回与列名称相关的错误

java - 在java中将IP在IPv4和数字格式之间转换

algorithm - 我如何计算复杂性

python - 如何返回 Python 数组中目标元素的索引?

c# - 对不同行长度的文件进行二分搜索