Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming / 1 / a / Solution

Use two array indices, advancing only the smaller current entry. Here and in Questions 1–4, code is structured Oberon-style pseudocode: RETURN exits a procedure, Some(x) and None distinguish success and absence, and AND short-circuits from left to right. Arithmetic is exact where the source asks us to ignore integer overflow.Let $z$ be the smallest common value, and let $a[p]=b[q]=z$. Existence implies $N,M>0$. A useful loop invariant is $0\le i\le p<N$, $0\le j\le q<M$, with no common value among the discarded prefixes $a[\mathrm{0..}i)$ and $b[\mathrm{0..}j)$. Initially the prefixes are empty. If $a[i]<b[j]$, then $a[i]$ cannot equal any entry of $b[j..M)$ because that sorted array is increasing; it cannot be a common value in the discarded prefix either. Moreover $i=p$ would imply $z=a[i]<b[j]\le z$, a contradiction. Thus $i<p$ and incrementing $i$ is safe. The other branch is symmetric.

Every guard and return therefore uses valid array indices, even without explicit bounds tests. The loop variant $(p-i)+(q-j)$ decreases on each iteration. At exit the equal entries form a common value no larger than $z$, hence equal $z$. There are at most $N+M-2$ increments and constant work per increment. The procedure returns the smallest common value in $O(N+M)$ time and $O(1)$ auxiliary space.