= 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`.
Back to article page
