= Solution
Replace the tail call by updates to local bounds and a local rank:
``
def selectIterative(k: Int, l: Int, r: Int): Int = {
require(0 <= l && l < r && r <= a.length)
require(0 <= k && k < r - l)
var low = l
var high = r
var rank = k
while (high - low > 1) {
val p = partition(low, high)
val pivotRank = p - low
if (rank == pivotRank) return a(p)
if (rank < pivotRank) high = p
else {
rank -= pivotRank + 1
low = p + 1
}
}
a(low)
}
``
The <loop invariant> says that $l\leq low<high\leq r$, $0\leq rank<high-low$, and selecting rank `rank` in the active segment yields the originally requested <order statistic>. The original segment's <multiset> is preserved, and outside it no entries change. The updates are exactly the recursive reductions proved in part (c). The <loop variant> is $high-low$; a non-returning iteration strictly decreases it. A one-entry segment has only rank zero, establishing the final return. \b[Auxiliary space is $O(1)$], rather than a potentially deep <call stack>.
Back to article page
