$ ./guess_the_languageProblem Solving — fill the blank
Problem Solving — fill the blank · hard · #336

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 (also accepted: 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 ▸