Java Reference
In-Depth Information
Searching Arrays
The
binarySearch()
method in the
Arrays
class will search the elements of a sorted array for a
given value using the binary search algorithm. This only works if the elements of the array are in
ascending sequence, so if they are not, you should call the
sort()
method to sort the array before
calling the
binarySearch()
method. There are eight overloaded versions of the
binarySearch()
method of the form that we saw with the
fill()
method earlier. The
boolean
type is excluded from
the nine types we saw, in this case as well.
binarySearch(
type
[] array,
type
value)
There is an additional version of the
binarySearch()
method for searching an array of type
Object[]
where you can supply a reference to a
Comparator
object as the fourth argument. All
versions of the method return a value of type
int
, which is the index position in
array
where
value
was found. If the value is not in the array, a negative integer is returned that is produced by taking the
value of the index position where the value would be if it was in the array, its sign reversing, and
subtracting 1. For instance, suppose you have an array of integers containing the element values 2, 4, 6,
8, and 10:
int[] numbers = {2, 4, 6, 8, 10};
You could search for the value 7 with the statement:
int position = java.util.Arrays.binarySearch(numbers, 7);
The value of
position
will be
-4
, because if 7 was inserted in the array, it would be the fourth item in
the array, or at index value 3 (remember that java arrays start at position zero). The return value is
calculated as
-3-1
, which is
-4
. Thus if the value sought is not in the array then the return value is
always negative.
Unless you are using a method that uses a comparator for searching arrays of objects, the class type of
the array elements must implement the
Comparable
interface. Here's how we could search for a string
in an array of strings:
String[] numbers ={"one", "two", "three", "four", "five", "six", "seven"};
java.util.Arrays.sort(numbers);
int position = java.util.Arrays.binarySearch(numbers, "three");
We have to sort the
numbers
array; otherwise the binary search won't work. After executing these
statements the value of
position
will be 6.
