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

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.