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.
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).