The collections api - Data Structures and Problem Solving Using Java - page 246

used Object as the return type, and we want to ensure backward compat-
ability. The two-parameter max combines the iterator pattern with the func-
tion object pattern to step through the collection, and at line 75 uses calls
to the function object to update the maximum item.

6.4.3 binary search

The Collections API implementation of the binary search is the static method
Arrays.binarySearch . There are actually seven overloaded versions—one for
each of the primitive types except boolean , plus two more overloaded versions
that work on Object s (one works with a comparator, one uses the default com-
parator). We will implement the Object versions (using generics); the other
seven are mindless copy-and-paste.

As usual, for binary search the array must be sorted; if it is not, the results
are undefined (verifying that the array is sorted would destroy the logarithmic
time bound for the operation).
If the search for the item is successful, the index of the match is returned.
If the search is unsuccessful, we determine the first position that contains a
larger item, add 1 to this position, and then return the negative of the value.
Thus, the return value is always negative, because it is at most -1 (which
occurs if the item we are searching for is smaller than all other items) and is at
least -a.length-1 (which occurs if the item we are searching for is larger than
all other items).
The implementation is shown in Figure 6.15. As was the case for the max
routines, the two-parameter binarySearch calls the three-parameter binarySearch
(see lines 17 and 18). The three-parameter binary search routine mirrors the
implementation in Figure 5.12. In Java 5, the two-parameter version does not
use generics. Instead, all types are Object . But our generic implementation
seems to make more sense. The three-parameter version is generic in Java 5.
We use the binarySearch method in Section 10.1.

binarySearch uses
binary search and
returns the index
of the matched
item or a negative
number if the item
is not found.

6.4.4 sorting

The Collections API provides a set of overloaded sort methods in the Arrays
class. Simply pass an array of primitives, or an array of Object s that imple-
ment Comparable , or an array of Object s and a Comparator . We have not pro-
vided a sort method in our Arrays class.

The Arrays class
contains a set of
static methods
that operate on
arrays.

void sort( Object [ ] arr )
Rearranges the elements in the array to be in sorted order, using the natural
order.