Java Reference
In-Depth Information
This algorithm required just three comparisons to determine whether the search key
matched an element of the array. Using a linear search algorithm would have required 10
comparisons. [
Note:
In this example, we've chosen to use an array with 15 elements so that
there will always be an obvious middle element in the array. With an even number of ele-
ments, the middle of the array lies between two elements. We implement the algorithm to
choose the higher of those two elements.]
Class
BinarySearchTest
(Fig. 19.3) contains:
•
static
method
binarySearch
to search an
int
array for a specified key
•
static
method
remainingElements
to display the remaining elements in the ar-
ray being searched, and
•
main
to test method
binarySearch
.
The
main
method (lines 57-90) is nearly identical to
main
in Fig. 19.2. In this program,
we create a 15-element array (line 62) and line 67 calls the
Arrays
class's
static
method
sort
to sort the array
data
's elements in an array in ascending order (by default). Recall
that the binary search algorithm will work only on a sorted array. The first line of output
from this program shows the sorted array of
int
s. When the user instructs the program to
search for
18
, the program first tests the middle element, which is
57
(as indicated by
*
).
The search key is less than
57
, so the program eliminates the second half of the array and
tests the middle element from the first half. The search key is smaller than
36
, so the pro-
gram eliminates the second half of the array, leaving only three elements. Finally, the pro-
gram checks
18
(which matches the search key) and returns the index
1
.
1
// Fig. 19.3: BinarySearchTest.java
2
// Use binary search to locate an item in an array.
3
import
java.security.SecureRandom;
4
import
java.util.Arrays;
5
import
java.util.Scanner;
6
7
public class
BinarySearchTest
8
{
9
// perform a binary search on the data
10
public static int
binarySearch(
int[]
data,
int
key)
11
{
12
int
low =
0
;
// low end of the search area
int
high = data.length -
1
;
// high end of the search area
int
middle = (low + high +
1
) /
2
;
// middle element
13
14
15
int
location =
-1
;
// return value; -1 if not found
16
17
do
// loop to search for element
18
{
19
// print remaining elements of array
20
System.out.print(remainingElements(data, low, high));
21
Fig. 19.3
|
Use binary search to locate an item in an array (the
*
in the output marks the middle
element). (Part 1 of 3.)
