Type RANDOMIZED-SELECT (CLRS 1-indexed): recurse on ONE side

Answer

RANDOMIZED-SELECT(A, p, r, i) if p == r: return A[p] q = RANDOMIZED-PARTITION(A, p, r) k = q - p + 1 if i == k: return A[q] elseif i < k return RANDOMIZED-SELECT(A, p, q-1, i) else return RANDOMIZED-SELECT(A, q+1, r, i-k)

k is the pivot’s rank in the subarray. If i equals k, the pivot is the answer; otherwise recurse into exactly one side (adjusting i on the right) — never both.