Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 2 / b / Solution 2026-10-31
View more
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.
Read the full article