Solution

ID: 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.

New to topics? Read the docs here!