Нет никаких гарантий для 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

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

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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

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

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