Никаких гарантий для Arrays.BinarySearch?

Question

http://java.sun.com/j2se/1.4.2/docs/api/java/util/Arrays.html

Sun не упоминает о каких-либо сложностях реализации бинарного поиска.Это ошибка?Я знаю, что так должно быть O(logn), но меня нервирует, когда об этом не говорят прямо.Они так и делают для некоторых своих алгоритмов, например Arrays.sort.

Есть ли у кого-нибудь из вас какие-либо знания о фактической реализации?У меня еще не было возможности скачать исходный код самостоятельно!Я думаю, это тривиальный двоичный поиск, но Sun иногда настраивает алгоритмы для повышения производительности.

Answer 1

Реализация java.util.Array является простым и не имеет места для оптимизации.

Исходный код вы найдете в JAVA_HOME/src.zip.Алгоритм сортировки в этом классе, который необходим для использования двоичного поиска, — это оптимизированная быстрая сортировка, обеспечивающая производительность n*log(n) (для многих наборов данных).

Answer 2

двоичный поиск по определению равен O(log n) (в среднем), думаю, нет необходимости упоминать об этом явно.

Answer 3

Arrays.sort гарантированно возвращает отсортированный массив, независимо от того, что содержит ваш массив.

Arrays.binarySearch(...) (кстати, строчная буква «b») не может гарантировать, что ваш массив может быть неотсортированным.

Теперь редактирую свой ответ:глядя на код, очевидно, что невозможно работать хуже, чем O (log n).Но, конечно, нет никакой гарантии, что вы найдете правильное значение.

Answer 4

Есть ли у кого-нибудь из вас какие-либо знания о фактической реализации?

Вы можете найти исходный код фактической реализации самостоятельно в вашей установке JDK или с помощью поиска Google.Например, найдите «java.util.Arrays.java.html».

Но я не сомневаюсь, что методы бинарного поиска O(logN).Если бы их не было, кто-нибудь бы это заметил...в последние 10 или около того лет.