Java Reference
In-Depth Information
Continued from previous page
Rather than returning
-1
for an unsuccessful search, the
Arrays.binarySearch
and
Collections.binarySearch
methods return (
-index - 1
), where
index
is the last index the algorithm examined before giving up, which is also the index
of the first element whose value is greater than the target. The documentation for
these methods calls this value the
insertion point
because if you wanted to add
the target to the array in sorted position, you'd place it at that index. For exam-
ple, because a binary search of the following array for the value
45
would finish
at index 5, the algorithm would return
-6
:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
11
18
29
37
42
49
51
63
69
72
77
82
88
91
98
If you were maintaining this sorted array and wanted to add
45
to it at the proper
index to retain the sorted order, you could call
Arrays.binarySearch
, get the
result of
-6
, negate it, and subtract 1 from it to get the index at which you should
insert the value. This is much faster than linearly searching for the place to add
the value or adding the value at the end and resorting the array.
We could modify our own binary search code to match Sun's behavior by changing
the last line of the method's body to the following line:
return -min - 1; // not found
Searching for a particular object in an array of objects requires a few modifications to
our searching code from the previous sections. Let's look at a sequential object
search first, because it will work with any type of object. The most important modifi-
cation to make to the code is to ensure that it uses the
equals
method to compare
objects for equality:
// Sequential search algorithm.
// Returns the index at which the target first
// appears in the given input array, or -1 if not found.
public static int indexOf(Object[] objects, Object target) {
for (int i = 0; i < objects.length; i++) {
if (objects[i].equals(target)) {
return i; // found it!
}
}
return -1; // not found
}
Search WWH ::
Custom Search