- Background 0 1 2 3 4 5 6 7 8 9 A Characteristic Of Efficient Search Algorithms Is That Each Probe Results In A Significa 1 (186.17 KiB) Viewed 27 times
at construction, with a "resident" matrix on which it can then
perform searches, via its findAll() method. That method
is provided with a search key (via its parameter) and its job is to
construct an ArrayList containing all the locations (each
in the form of a GridLocation object) at which the search
key occurs (within the resident matrix, of course).
That ArrayList can then be retrieved by the client
program by calling the getLocs() method.
import java.util.ArrayList;
public class RecSaddleBackSearcher {
// instance variables
// ------------------
private int probeCntr; // # probes performed
since last reset
private int[][] matrix; // resident matrix (in which
searches occur)
private int key; // value
most recently searched for
// list of locations at which the search key was
found during the most
// recent call to findAll()
private ArrayList<GridLocation> locList;
// constructor
// -----------
/* Establishes the resident matrix of this
RecSaddleBackSearcher.
** It is verified that the values in the matrix
increase along each
** row and column. If not, an
IllegalArgumentException is thrown.
*/
public RecSaddleBackSearcher(int[][] ary) {
if (isValidMatrix(ary)) {
matrix = ary;
resetProbeCount();
}
else {
throw new
IllegalArgumentException("Unsuitable matrix");
}
}
// observer
// --------
/* Returns (a reference to) the resident
matrix.
*/
public int[][] residentMatrix() { return matrix; }
/* Returns the number of probes performed since the
last time
** the probe counter was reset.
*/
public int probeCount() { return probeCntr; }
/* Returns the key that was searched for by the
most recent call
** to findAll().
*/
public int getKey() { return key; }
/* Returns the list of locations produced by the
most recent call
** to findAll().
*/
public ArrayList<GridLocation> getLocs() {
return locList; }
// mutators
// --------
/* Resets the probe counter to zero.
*/
public void resetProbeCount() { probeCntr = 0; }
/* Builds an ArrayList (which subsequently can be
retrieved via a call to
** getLocs()) containing all the locations in the
resident matrix at which
** the given key occurs.
*/
public void findAll(int key) {
this.key = key;
locList = new
ArrayList<GridLocation>();
int numRows = matrix.length;
int numCols = matrix[0].length;
GridLocation bottom = new
GridLocation(0,0);
GridLocation top = new GridLocation(numRows-1,
numCols-1);
findAllAux(bottom, top);
}
// private methods
// ---------------
/* Adds to the ArrayList 'locList' (an instance
variable) all the
** locations that contain the search key (instance
variable 'key')
** within the specified rectangular region of the
resident matrix.
*/
private void findAllAux(GridLocation lowCorner,
GridLocation highCorner) {
if (isEmptyRegion(lowCorner, highCorner))
{
// do nothing, as an empty region
contains no occurrences of the key
}
else {
// recursive case, needing to
be completed
}
}
/* Reports whether the rectangular region described by
the given corner
** locations is empty.
*/
private boolean isEmptyRegion(GridLocation
lowCorner,
GridLocation
highCorner) {
return lowCorner.ROW > highCorner.ROW
||
lowCorner.COL >
highCorner.COL;
}
/* Returns the lowest-numbered location within
a[low..high] containing
** a value that is >= the given key, or high+1 if
no such location exists.
** pre: low <= high+1 and values in a[low..high]
are in ascending order.
*/
private int binarySearch(int[] a, int low, int high,
int key) {
int left = low;
int right = high+1;
while (left != right) {
probeCntr++;
int mid = (left + right) /
2;
if (a[mid] < key)
{
left = mid+1;
}
else { // a[mid] >= key)
{
right = mid;
}
}
return left;
}
/* Reports whether or not the given two-dimensional
array satisfies
** the conditions required here. One condition
is that all rows
** have the same length. The other condition is
that the values
** increase along each row and each column.
*/
private boolean isValidMatrix(int[][] ary) {
boolean result;
if (!isRectangular(ary)) {
result = false;
}
else { // ary is rectangular; check rows
and columns.
result = true;
int r = 0;
while (r != ary.length
&& result) {
// check row r
result =
isIncreasing(ary[r]);
r = r+1;
}
// Now check columns
int numCols =
ary[0].length;
int c = 0;
while (c != numCols
&& result) {
result =
isIncreasingColumn(ary, c);
c = c+1;
}
}
return result;
}
/* Reports whether the values in the given array
are in
** increasing order.
*/
private boolean isIncreasing(int[] b) {
int i = 1;
while (i < b.length &&
b[i-1] < b) {
i = i+1;
}
return i >= b.length;
}
/* Reports whether the values in the specified
column within
** the given two-dimensional array are in increasing
order.
** pre: Every row in b[][] has at least col+1
columns.
*/
private boolean isIncreasingColumn(int[][] b, int col)
{
int i = 1;
while (i < b.length &&
b[i-1][col] < b[col]) {
i = i+1;
}
return i >= b.length;
}
/* Reports whether the given two-dimensional array
is rectangular
** (meaning that all its rows have the same
length).
** pre: b.length != 0
*/
private boolean isRectangular(int[][] b) {
int numCols = b[0].length;
int i = 1;
while (i < b.length &&
b.length == numCols) {
i = i+1;
}
return i >= b.length;
}
}
public class GridLocation {
public final int ROW;
public final int COL;
public GridLocation(int r, int c) {
ROW = r; COL = c;
}
public String toString() {
return "(" + ROW + ',' + COL + ')';
}
}
Background 0 1 2 3 4 5 6 7 8 9 A characteristic of efficient search algorithms is that each probe results in a significant decrease in the size of the search space. As you will recall, in the binary search algorithm, each time an array element is probed (i.e., accessed and compared to the search key), the search space is cut in half. That algorithm exploits the fact that the array elements are in ascending order. (Indeed, binary search is not applicable unless the array elements are in ascending (or, alternatively, descending) order.) 0 4 6 9 10 12 15 19 22 24 25 1 5 10 11 12 13 18 21 24 26 27 2 6 14 18 21 23 24 26 29 30 33 3 [10 15 19 24 25 27 31 34 36 37 4 11 17 23 25 29 31 33 38 42 43 5 115 18 27 29 30 32 35 42 46 50 6 16 19 30 34 35 37 41 43 50 51 | 7 20 23 32 37 41 43 44 47 52 53 8 24 25 33 40 45 46 49 50 54 57 9 26 29 34 41 48 51 55 58 60 62 | 10 30 33 38 43 52 56 58 61 64 67|| Can the binary search algorithm be generalized to find occurrences of values in a two- dimensional array (i.e., matrix)? The answer is yes, assuming, of course, that its elements are properly ordered. For the purposes of this assignment, that will mean that the elements are strictly increasing along each row and along each column. An example of a 10x11 matrix —call it M-satisfying this condition is shown to the right. 10x11 matrix M Observe that, in any rectangular region of such a matrix, the largest value is found in its high corner (i.e., bottom right) and its smallest value is found in its low corner (i.e., upper left). a To illustrate how one can apply the binary search concept to such a matrix, suppose that we wish to find the locations in M at which 38 occurs. 0 1 2 3 4 5 6 7 8 9 0 The low corner of M is at location (0,0) and its high corner is at location (10,9). We can compute 1 15 19 22 24 25 18 21 24 26 27|
the middle location to be (0+10)/2, (0+9)/2), or (5,4). There we find 30, which is less than our search key, 38. It follows that 38 cannot possibly occur in the region whose high corner is (5,4), because all values in that region must be 30 or less. Which means that, as the result of this single probe, we can eliminate one-fourth of the search space from further consideration, as illustrated to the right. 2 | 3 41 5 ELIMINATED 24 26 29 30 33 27 31 34 36 37 |31 33 38 42 43 30 32 35 42 46 50 The remaining search space (all of which must be searched if we are to be sure to find all locations in which 38 occurs) can be interpreted in three different ways: 6 16 19 30 34 35 37 41 43 50 51 7 20 23 32 37 41 43 44 47 52 53 8 24 25 33 40 45 46 49 50 54 57 9 26 29 34 41 48 51 55 58 60 62 10 30 33 38 43 52 56 58 61 64 67 After one probe in search of 38 1. As three rectangular regions, namely o low corner: (0,5); high corner: (5,9) low corner: (6,0); high comer: (10,4) o low corner: (6,5); high corner: (10,9) 2. As two rectangular regions, namely o low corner: (0,5); high corner: (10,9) o low corner: (6,0); high corner: (10,4) 3. As two rectangular regions, namely low corner: (0,5); high corner: (5,9) low corner: (6,0); high comer: (10,9) Of course, to search in any of the remaining rectangular regions, we can employ the same approach that got us this far. In other words, we search each of the remaining rectangular regions recursively! (The base case would be an empty region.) 0 1 2 3 4 5 6 7 8 9 Now suppose that our search key had been 20 rather than 38. Then the conclusion that we would have drawn from our initial probe to location (5,4) (which contains 30) is that there is no need to perform any more probes within the region whose low corner is (5,4). The situation is shown to the right. 04 6 9 10 12 15 19 22 24 25 1 5 10 11 12 13 18 21 24 26 27 2 6 14 18 21 23 24 26 29 30 331
bu 10 15 19 24 25 27 31 34 36 37 11 17 23 25 29 31 33 38 42 43 4 As before, we can interpret the remaining search space to be either a collection of three rectangular regions or, in two different ways, a pair of rectangular regions. In any case, we would then be left to recursively search the relevant regions. ELIMINATED The figures below attempt to generalize the examples described above and to address the possibility that the element probed happens to be the search key. The assumption is that a search for x is to be carried out within a rectangular region whose low corner has coordinates (LR,LC) and whose high corner has coordinates (HR,HC). The coordinates of the middle location are (MR.MC), where MR = (LR + HR)/2 and MC = (LC + HC)/2. 5 15 18 27 29 30 6 16 19 30 34 7 20 23 32 37 8 24 25 33 40 9 26 29 34 41| 10 130 33 38 43 After one probe in search of 20 LC MC HC LC MC HC LC MC HC LR LR LR LR LR LR ELIMINATED 1 ELIMINATED 1 | MR <X MR MR >x MR MR x MR 「 ELIMINATED ELIMINATED HR HR HR HR HR HR । । LC MC HC LC MC HC LC MC HC When middle When middle When middle
element <search key element > search key element = search key A Possibly Better Approach Notice how, if our probe of the region's middle element is lucky enough to find the search key there, fully half of the search space can be eliminated from further consideration. In the other two cases, only a fourth of that space can be eliminated. It is a huge advantage, in terms of minimizing the number of probes performed during a search, to be able to eliminate half of the search space, as opposed to only one-fourth. But perhaps we can make our own luck! Suppose that instead of simply probing the middle element of the region being searched, we performed a binary search within that region in order to find a pair of adjacent locations whose values are, respectively, less than and not less then, the search key. Such a search could take place within, say, the middle row of the region. The result of such a search allows us to eliminate fully half the search space, like this: LC HC LR LR ELIMINATED F MR </2 MR ELIMINATED
HR HR LC C HC To clarify, here we performed a binary search within the middle row MR of the indicated region of matrix M to find c satisfying the condition that M[MR][c-1] <x and M[MR][C] > X. Having found c, fully half of the search space can be eliminated. Of course, finding c costs about lg(HC-LC+1) probes (in performing binary search upon a row of length HC-LC+1) rather than only one. An interesting question is whether performing a logarithmic number of probes to be able to eliminate half the search space results in a fewer total number of probes than does using one probe for the purpose of eliminating one-fourth of the search space. Note: One must also allow for these possibilities: • c = HC+1, which occurs if the search key is larger than M[MR][HC]. In this case, the top half of the region, rows LR through MR, can be eliminated. • c=LC, which occurs if the search key is less than or equal to M[MR][LC]. In this case, the bottom half of the region, rows MR through HR, can be eliminated. Although one might fairly call these special cases, it is not necessarily true that they must be treated totally differently from the "normal" case. The Assignment Provided are the following Java classes, the last of which is in need of completion. Gridlocation. An instance of this utility class representen location onoridor within a matriy expressed in terms of a row