randomized divide-and conquer algorithm RAND-SELECT(A, p, g, i) bith smallest of.. g if p=g then return alp r<RAND-PARTITION(A, P, q k p+ >k=rank(A[rD if i=k then return a[rI if i<k then return RaNd-seleCt(A, p, r-1, i) else return RAND-SELECT(A, r+1, g, i-k) ≤A[ ≥A[r o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6.3© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.3 Randomized divide-and￾conquer algorithm RAND-SELECT(A, p, q, i) ⊳ ith smallest of A[p . . q] if p = q then return A[p] r ← RAND-PARTITION(A, p, q) k ← r – p + 1 ⊳ k = rank(A[r]) if i = k then return A[r] if i < k then return RAND-SELECT(A, p, r – 1, i) else return RAND-SELECT(A, r + 1, q, i – k ) ≤≤AA[r] [r] ≥≥AA[r] [r] p q r k