我正在尝试解决这个问题。
给定n个数字的列表，我们想从列表中找到最小和第二小的数字。描述解决该问题的分治算法。假设对于整数k，n = 2 ^ k。即使在最坏的情况下，使用您的算法进行的比较次数也不应超过3n / 2 − 2。
我当前的解决方案是使用选择算法来获取中位数，然后将列表划分为L1（包含小于或等于中位数的元素），R（中位数），L2（包含比中位数更大的所有元素）。这是正确的吗？如果是这样，我下一步该怎么做？
请注意，中位数选择算法使用Θ（n）比较，但这并不意味着它最多使用3n / 2-2个比较。实际上，我认为它使用的更多，这可能会排除您的解决方案策略。
提示：将这个问题视为对所有2 k进行淘汰赛；每个回合的胜者（两个数字中较小的一个）进入下一轮。要实现这一点需要进行多少次比较？接下来，请注意，第二个最小的数字必须“丢失”到最小的数字。第二小的数字也是“丢失”到最小数字的最小数字。鉴于此，您可以有效地找到第二小的数字吗？
希望这可以帮助！
