Search code examples
algorithmpruning

Having difficulty in Prune and Search Algorithm

enter image description here

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 |S1| + |S2| ≥ k -- I'm not even sure if it's an absolute value or what. I don't get the iterations too. Uhmm

Solution

  • 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.