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

Keep the target as an absolute, zero-based array index:

function Find(i; var a; l, r): T
    require l <= i < r
    Partition(a,l,r,m,n)
    if i < m then
        return Find(i,a,l,m)
    else if i >= n then
        return Find(i,a,n,r)
    else
        return a[i]

The order statistic belongs to the lower segment, equality interval or upper segment according to the index comparison. In the middle interval its value is the pivot; otherwise Quickselect recurses only into the relevant outer interval. The nonempty equality interval guarantees a strictly shorter retained segment. The procedure sorts neither discarded segment. Since indices remain absolute, the right recursion does not subtract n from i.