No guarantees for Arrays.BinarySearch?

Question

http://java.sun.com/j2se/1.4.2/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.

Answer 1

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 2

binary search is by definition O(log n) (on average) guess there's no need to mention it explicittly.

Answer 3

Arrays.sort is 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.

Answer 4

Does any of you have any knowledge of the actual implementation?

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.