Java Reference
In-Depth Information
For example, if d is the array
{{2,8,1,7}, {5,2,7,8}, {2,3,5,6}}
, then
the call
search(d, 5)
produces the pair
(1,0)
because the first occurrence of
5
in
d
occurs in row
1
, column
0
.
The elements of
d
are to be processed in row-major order, where “process-
ing an element” means returning from the function if the element equals
x
. We
can use the loop schema of Fig. 9.3. The function itself is given in Fig. 9.5.
The invariant came from refining the meaning of “process an element” in
this context. The loop repetend was refined as well: If
x
equals the array element
being processed, a new instance of class
Coordinates
is created and returned.
And, when the loop terminates normally, then, as per the specification of the
method, the value returned is an instance
(d.length, 0)
of class
Coordinates
.
The use of the schema made for a rapid development of this function.
9.2.5
Saddleback search
Suppose
m
by
n
array d satisfies this property: every row is non-descending and
every column is non-descending. Under these conditions, we hope that we can
search the array for a value faster than row-major order search does, which takes
time proportional to
m*n
in the worst case. But how do we search it faster?
Activity 9-2.5 of the CD develops a perfectly delightful algorithm for searching
the array. The idea for the algorithm is not pulled out of a magician's hat but
comes from following the principle of finding a loop invariant before writing
the loop. The development is much more effective in a lecture, so we leave it to
activity 9-2.5 of the
ProgramLive
CD.
Get the schema
from a footnote
on lesson page
9-2.
9.3
Arrays of arrays
Previously, we said that a variable b declared as
int
[][] b= {{5, 6, 2}, {1, 4, 8}};
contained the name of a rectangular array. While this view can be used, we gain
/** =
first index
(r, c)
in row-major order of
x
in
d
, or
(d.length, 0)
if
x
not in
d */
public static
Coordinates search(
int
[][] d,
int
x) {
//
invariant:
d[0..r-1]
and
d[r][0..c-1]
do not contain
x
for
(
int
r= 0; r != d.length; r= r + 1)
for
(
int
c= 0; c != d[r].length; c= c + 1) {
if
(
d[r][c]) == x)
{
return new
Coordinates(r, c); }
}
return new
Coordinates(d.length, 0);
}
Figure 9.5:
A row-major search function
Search WWH ::
Custom Search