Java Reference
In-Depth Information
looking for. Hence, we should look in the second half of the array for a match, that is,
in the sequence:
652
Now the last value of the first half of this sequence is 17; hence, the value must be
located in the sequence:
The last value of the first half of this very short sequence is 12, which is smaller than
the value that we are searching, so we must look in the second half:
It is trivial to see that we don't have a match, because 15 ʋ 17. If we wanted to insert
15 into the sequence, we would need to insert it just before
a[5]
.
A binary search locates a value in a sorted array by determining whether the value
occurs in the first or second half, then repeating the search in one of the halves.
This search process is called a binary search, because we cut the size of the search in
half in each step. That cutting in half works only because we know that the sequence
of values is sorted.
The following class implements binary searches in a sorted array of integers. The
search
method returns the position of the match if the search succeeds, or
-1
if
v
is
not found in
a
.
ch14/binsearch/BinarySearcher.java
1 /**
2
A class for executing binary searches through an array.
3 */
4
public class
BinarySearcher
5 {
