Java Reference
In-Depth Information
25 {
26
int
pos = searcher.search(n);
27 System.out.
println(
ÐFoundinpositionÑ
+ pos);
28 }
29 }
30 }
31 }
Typical Output
[46, 99, 45, 57, 64, 95, 81, 69, 11, 97, 6, 85,
61, 88, 29, 65, 83, 88, 45, 88]
Enter number to search for, -1 to quit:
11
Found in position 8
S
ELF
C
HECK
11.
Suppose you need to look through 1,000,000 records to find a telephone
number. How many records do you expect to search before finding the
number?
12.
Why can't you use a Ȓfor eachȓ loop for (
int element : a
) in the
search
method?
14.7 Binary Search
Now let us search for an item in a data sequence that has been previously sorted. Of
course, we could still do a linear search, but it turns out we can do much better than
that.
Consider the following sorted array
a
. The data set is:
We would like to see whether the value 15 is in the data set. Let's narrow our search
by finding whether the value is in the first or second half of the array. The last point
in the first half of the data set,
a [3]
, is
9
, which is smaller than the value we are
651
