Java Reference
In-Depth Information
The figure shows two searches of an array of integers. The first step is always to compare the target with
the element at the approximate center of the array. The second step is to examine the element at the approx-
imate center of the left or right half of the array, depending on whether the target is less than or greater than
the element. This process of subdividing and examining the element at the middle of the interval continues
until the target is found, or the interval consists of a single element that is different from the target. When
the target is found, the result is the index position of the element that is equal to the target. You should be
able to see that the algorithm implicitly assumes that the elements are in ascending order.
You have eight overloaded versions of the
binarySearch()
method supporting the range of types that
you saw with
fill()
:
binarySearch(
type
[] array,
type
value)
The second argument is the value you are searching for. You have an additional version of the method for
searching an array of type
T[]
for which you can supply a reference to a
Comparator<? super T>
object as
the third argument; the second argument is the value sought. You also have a version that will search a part
of an array:
binarySearch(T[] array, int from, int to, T value, Comparator<? super T> c)
This searches the elements from
array[from]
to
array[to-1]
inclusive for
value
.
All versions of the
binarySearch()
method return a value of type
int
that is the index position in
array
where
value
was found. Of course, it is possible that the value is not in the array. In this case a negative
integer is returned. This is produced by taking the value of the index position of the first element that is
