Implement staircase matrix search from the top-right corner. In the following Oberon-style code, The loop invariant is that every occurrence not yet returned lies inInitially 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.
& 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 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
Articles by others on the same topic
There are currently no matching articles.