What goes in the blank?
# quickselect: k-th smallest, p = pivot's final index
if k == p:
return a[p]
elif k < p:
return select(a, lo, ____ - 1, k)
else:
return select(a, p + 1, hi, k)
Answer: p
After partitioning, everything left of p is smaller, so the k-th smallest lies in [lo, p - 1]. Only one side is searched, giving O(n) average time.
Play Problem Solving ▸