Sorting and Searching - Java Concepts - page 893

The Arrays class contains a static binarySearch method that implements the
binary search algorithm, but with a useful enhancement. If a value is not found in the
array, then the returned value is notɨ 1, butɨkɨ1, where k is the position before
which the element should be inserted. For example,
int[] a = { 1, 4, 9 };
int v = 7;
int pos = Arrays.binarySearch(a, v);
// Returns -3; v should be inserted before
position 2
S ELF C HECK
13. Suppose you need to look through a sorted array with 1,000,000
elements to find a value. Using the binary search algorithm, how many
records do you expect to search before finding the value?
14. Why is it useful that the Arrays.binarySearch method indicates
the position where a missing element should be inserted?
15. Why does Arrays.binarySearch returnɨkɨ1 and notɨk to
indicate that a value is not present and should be inserted before position
k?
14.8 Sorting Real Data
In this chapter we have studied how to search and sort arrays of integers. Of course,
in application programs, there is rarely a need to search through a collection of
integers. However, it is easy to modify these techniques to search through real data.
The sort method of the Arrays class sorts objects of classes that implement the
Comparable interface.
The Arrays class supplies a static sort method for sorting arrays of objects.
However, the Arrays class cannot know how to compare arbitrary objects. Suppose,
for example, that you have an array of Coin objects. It is not obvious how the coins
should be sorted. You could sort them by their names, or by their values. The
Arrays. sort method cannot make that decision for you. Instead, it requires that