Solution

Use half-open rectangles

[r_{0}, r_{1}) \times [c_{0}, c_{1})

. Split the longer dimension at its middle. If rows are the longer dimension, binary search the middle row for its first entry at least

x

. 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

x

and entries from hi onward are at least

x

, within the splitting row or column. At its end, either equality is found or the splitting line is strictly separated around

x

. 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

Bisect the longer dimension, binary-search the splitting line, recurse on the two opposite rectangles.

(1)

Figure 1.
Two complementary rectangles survive a middle-row search
. For a monotone matrix, the middle row's binary search separates entries smaller than $x$ from entries greater than $x$ when no equality is found. The upper-left and lower-right rectangles are excluded by monotonicity; only the blue and orange rectangles require further search algorithm. **Details**.

 Ancestors (12)

 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

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 2 / f / Solution

 Ancestors (12)

 Discussion (0)  Subscribe (1) New discussion

 Articles by others on the same topic (0)

 Discussion (0) New discussion