Having difficulty in Prune and Search Algorithm

Question

I do understand Input until step 4 (If my understanding is correct) but step 5 is a bit confusing because I don't know what should I put in |S₁| + |S₂| ≥ k -- I'm not even sure if it's an absolute value or what. I don't get the iterations too. Uhmm

Answer 1

So after step 4:

• S1 contains element smaller than p
• S2 contains several occurences of p and only p's
• S3 contains element greater than p

Therefore

• if |S1| > k then it contains the k-th element of S
• else if |S1| + |S2| > k then S2 contains the k-th element of S which is therefore p
• else the k-th element of S in in S3. So searching the k-th element of s is the same as searching the (k-|S1|-|S2|) element of S3. Therefore you restart (ie iterate) the same algorithm with S = S3 and k=k-|S1|-|S2|.

Hope this help.