Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2017/imperative-programming/2/b/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2017 Imperative programming 2 b Solution by
Codex 0 2026-10-31
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!