Question 1 (25 points)
Complete
the definition of method Search below, which stops as
soon as it finds an element A[ r ][ c ]
equal to val. Do not use any additional loop constructs
other than the given while-loop.
Solution 1
static boolean search( int[][] A, int val )
{
int h = A.length;
int w =
A[ 0 ].length;
int r = 0;
int c = 0;
while ( r <
h && A[ r ][ c ] != val )
{
if ( c == (w
- 1) )
{
c = 0;
r++;
}
else c++;
}
return r <
h;
}
Solution 2
static boolean search( int[][] A, int val )
{
int h =
A.length;
int w = A[ 0
].length;
int r = 0;
int c = 0;
while ( A[ r
][ c ] != val && (r != h -1 || c != w-1)
{
if ( c == (w - 1) )
{
c = 0;
r++;
}
else c++;
}
return A[ r ][
c ] == val;
}
Solution 3
static boolean search( int[][] A, int val )
{
int h =
A.length;
int w = A[ 0
].length;
int r = 0;
int c = 0;
while ( A[ r
][ c ] != val )
{
if ( c == (w
- 1) )
{
if ( r == h
- 1 )
return
false;
c = 0;
r++;
}
else c++;
}
return true;
}
Comments
There
are numerous variations on these solutions. This is an interesting problem
because it allows such a variety of ways of approaching it.
This
problem was done only moderately well by the examinees. There were two main problems, and we
encourage students preparing for the final to pay attention. First, in setting up a boolean conditional,
the order of the operands in the conditional matter. The left operand of a binary expression is evaluated before the
right. So in Solution 1, switching the
order of the tests would be quite wrong, as even if r equals h, A[r][c]
== val will
be tested first, and the code will throw an index out of bounds exception. (Examinees
should note how Solution 2 manages to circumvent this problem). Second, an && test will fail if
either of its operands is false: code whose execution depends upon the outcome
of such a test must be capable of handling each situation. A great many students ruined an otherwise
correct version to Solution 1 by returning A[r][c] == val instead of r < h or r
!= h. If the while loop exits because r equals h,
then that statement will throw an exception (again, Solution 2 avoids this
problem of its particular testing condition).
We
note that Solution 3, while correct, has two return statements; this is
generally considered bad style.