Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming resit / 2 / b

For an integer pivot $0\le p\le N+1$, exactly $k$ entries lie in $[0,p)$. That interval contains $p$ possible integers. If $k<p$, the pigeonhole principle implies that some value in $[0,p)$ is missing. Counting occurrences rather than distinct entries only strengthens this argument: $k$ occurrences cannot cover more than $k$ distinct values.

For completeness, if $p>N+1$ the lower side contains the entire permitted value range, which already has a missing value. If $p\le 0$, the condition $k<p$ is impossible. Thus the general conclusion is a missing permitted value below $p$; an internal pivot gives useful localization.

There are $N-k$ entries in $[p,N+1)$, which contains $N+1-p$ possible integers. If $k\ge p$, then $N-k\le N-p<N+1-p$. Therefore some value in $[p,N+1)$ is missing, again by the pigeonhole principle. This is an existence conclusion in the chosen interval, not a claim that all missing values lie there; both sides can contain missing values when duplicates occur.

If $p\le 0$, the upper side contains the whole permitted range and hence a missing value. If $p>N+1$, the condition $k\ge p$ is impossible. Outside the internal-pivot range this conclusion therefore supplies no improved localization.