algorithm - 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

所以在第4步之后：

• S1 包含小于 p 的元素
• S2 包含多次出现的 p 并且只有 p
• S3 包含大于 p 的元素

所以

• 如果|S1| > k那么它包含 S 的第 k 个元素
• else if |S1| + |S2| > kthen S2 包含 S 的第 k 个元素，因此是 p
• 否则 S3 中 S 的第 k 个元素。所以搜索 s 的第 k 个元素与搜索(k-|S1|-|S2|)S3 的元素是一样的。S = S3因此，您使用and重新启动（即迭代）相同的算法k=k-|S1|-|S2|。

希望这有帮助。