Searching and Sorting - Building Java Programs: A Back to Basics Approach - page 798

Did You Know?
Binary Search Details
There are a few interesting things about Sun's implementation of binary search
in Arrays.binarySearch and Collections.binarySearch that we haven't
mentioned yet. Take a look at this text from the Javadoc documentation of Sun's
binarySearch method:
“The array must be sorted (as by the sort method, above) prior to making
this call. If it is not sorted, the results are undefined. If the array contains
multiple elements with the specified value, there is no guarantee which one
will be found.”
Binary search depends on the array being sorted. If it isn't sorted, Sun says the
results are undefined. What does that mean? Why doesn't the algorithm just sort
the array for you if it's unsorted?
There are two problems with that idea, both essentially related to runtime per-
formance. For one, sorting takes much longer ( O ( N log N ) time) than a binary
search ( O (log N ) time). Second, to even discover that you need to sort the array,
you'd need to look at each element to determine whether they're in order, which
takes O ( N ) time. Essentially, the cost of examining the array and sorting it if nec-
essary would be too great.
Even if the cost of sorting the array weren't so large, the client of the
binarySearch method probably won't want its array modified by the
binarySearch method. Searching is supposed to be a read-only operation, not one
that rearranges the array.
Let's look at the other part of the previous quote: “If the array contains multi-
ple elements with the specified value, there is no guarantee which one will be
found.” We didn't mention this earlier when we were discussing the algorithm,
but in the case of duplicates, binary search isn't guaranteed to find the first
occurrence of the element, because the moment it finds an occurrence it stops.
Here's another interesting blurb from the binarySearch documentation:
Returns: index of the search key, if it is contained in the list; otherwise,
(-(insertion point) - 1) . The insertion point is defined as the point
at which the key would be inserted into the list: the index of the first ele-
ment greater than the key, or list.size() , if all elements in the list are
less than the specified key. Note that this guarantees that the return value
will be >= 0 if and only if the key is found.
Continued on next page