With the fixed array f visible to the procedures, use a Boolean result for success and two output array indices:
TYPE Search = PROCEDURE(x: INTEGER; VAR i, j: INTEGER): BOOLEAN;
On success, , , and . On failure there is no occurrence; the output indices are unspecified. Thus
(1)
Use a linear search over every pair of array indices.
PROCEDURE SearchAll(x: INTEGER; VAR i, j: INTEGER): BOOLEAN;
VAR r, c: INTEGER;
BEGIN
  FOR r := 0 TO M-1 DO
    FOR c := 0 TO N-1 DO
      IF f[r,c] = x THEN i := r; j := c; RETURN TRUE END
    END
  END;
  RETURN FALSE
END SearchAll;
For a worst-case lower bound, consider an input in which every inspected element differs from . If an element remains uninspected, changing just that element to gives an indistinguishable execution requiring the opposite answer. Therefore a correct exact search algorithm must inspect all elements in the worst case.
The printed phrase “at least ” uses the upper-bound notation for a lower-bound claim. Its precise interpretation is
(1)
This is an adversary argument for access to arbitrary independent array entries.
Write , assuming . By monotonicity, is at least every value in the first row and at most every value in the last column. Hence
(1)
The same observation applies to the top-right corner of any remaining rectangular subarray of this monotone matrix.
Implement staircase matrix search from the top-right corner. In the following Oberon-style code, & denotes short-circuit conjunction; all guarded accesses respect array bounds.
PROCEDURE Staircase(x: INTEGER; VAR i, j: INTEGER): BOOLEAN;
VAR r, c: INTEGER;
BEGIN
  r := 0; c := N-1;
  WHILE (r < M) & (c >= 0) DO
    IF f[r,c] = x THEN i := r; j := c; RETURN TRUE
    ELSIF f[r,c] < x THEN INC(r)
    ELSE DEC(c)
    END
  END;
  RETURN FALSE
END Staircase;
The loop invariant is that every occurrence not yet returned lies in
(1)
Initially this is the whole array. If , every entry of row in the candidate rectangle is smaller than , so increasing discards no possible answer. If , every entry of column in that rectangle is greater than , so decreasing is safe. These conclusions follow from monotonicity even when repeated values occur.
The loop variant decreases on every unsuccessful iteration. If a dimension becomes empty, the loop invariant proves absence. For positive dimensions the path inspects at most entries; an initially empty dimension causes no inspection. Thus
(2)
Monotonicity gives two excluded rectangles:
(1)
Indeed the first entries are at most , and the second are at least . In particular, the entire splitting row contains no answer. The only remaining candidates are the upper-right rectangle and the lower-left rectangle . These are the exclusions guaranteed by the given adjacent inequalities; further comparisons may exclude more.
Use half-open rectangles . Split the longer dimension at its middle. If rows are the longer dimension, binary search the middle row for its first entry at least . Equality returns immediately; otherwise part (e) leaves only an upper-right and a lower-left rectangle. A middle-column split uses the transposed argument.
PROCEDURE SearchRect(x, r0, r1, c0, c1: INTEGER;
                     VAR i, j: INTEGER): BOOLEAN;
VAR mid, lo, hi, k: INTEGER;
BEGIN
  IF (r0 >= r1) OR (c0 >= c1) THEN RETURN FALSE END;
  IF r1-r0 >= c1-c0 THEN
    mid := r0 + (r1-r0) DIV 2;
    lo := c0; hi := c1;
    WHILE lo < hi DO
      k := lo + (hi-lo) DIV 2;
      IF f[mid,k] < x THEN lo := k+1 ELSE hi := k END
    END;
    IF lo < c1 THEN
      IF f[mid,lo] = x THEN i := mid; j := lo; RETURN TRUE END
    END;
    IF SearchRect(x, r0, mid, lo, c1, i, j) THEN
      RETURN TRUE
    END;
    RETURN SearchRect(x, mid+1, r1, c0, lo, i, j)
  ELSE
    mid := c0 + (c1-c0) DIV 2;
    lo := r0; hi := r1;
    WHILE lo < hi DO
      k := lo + (hi-lo) DIV 2;
      IF f[k,mid] < x THEN lo := k+1 ELSE hi := k END
    END;
    IF lo < r1 THEN
      IF f[lo,mid] = x THEN i := lo; j := mid; RETURN TRUE END
    END;
    IF SearchRect(x, r0, lo, mid+1, c1, i, j) THEN
      RETURN TRUE
    END;
    RETURN SearchRect(x, lo, r1, c0, mid, i, j)
  END
END SearchRect;

PROCEDURE DivideSearch(x: INTEGER; VAR i, j: INTEGER): BOOLEAN;
BEGIN
  RETURN SearchRect(x, 0, M, 0, N, i, j)
END DivideSearch;
The lower-bound binary search invariant says that entries before lo are smaller than and entries from hi onward are at least , within the splitting row or column. At its end, either equality is found or the splitting line is strictly separated around . Endpoint cuts lo=c0, lo=c1, lo=r0, or lo=r1 are valid and merely make one candidate rectangle empty.
The recursion invariant is that the current rectangle contains every still-possible answer assigned to that call. The discarded rectangles are excluded by monotonicity; both retained rectangles inherit monotonicity. Each nonempty child has a strictly smaller longest dimension after at most two levels, so the recursion terminates, including one-row and one-column cases. The concise construction is
(1)

Ancestors (10)

  1. Imperative programming
  2. 2015
  3. Past exam of the year 1 of the computer science course of the University of Oxford
  4. Year 1 of the computer science course of the University of Oxford
  5. Computer science course of the University of Oxford
  6. Undergraduate course of the University of Oxford
  7. Course of the University of Oxford
  8. University of Oxford
  9. List of universities
  10. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version