algorithm - 找到中位数的下限

Question

假设我们有一个包含 n 个数字的列表，并且我们想要找到一个大于或等于中位数的数字。我想了解这个问题的最坏情况复杂性的下限。我知道找到中位数的下限是 3(n-1)/2。但是当我们要找一个大于或等于中位数的数时会不会一样。

Answer 1

我认为列表前半部分的最大元素（+1）将具有此功能。如果您检查 n/2+1 元素并存储最大的元素，则最多可能有 n/2-1 个元素大于您的中值候选人。因此，所选数字将位于数字的上半部分，这意味着：它大于或等于中位数。

所以你可以在n/2+1.

你需要：

最坏情况：n/2 次比较和 n/2+1 次分配。

最佳情况：n/2 次比较和 1 次分配。

Edit:回答您的评论：

是的。如果n是偶数，则任何随机元素将大于或等于中位数的概率至少为0.5。为什么“至少 0.5”？可能存在测试用例，其中几乎所有数字都等于中位数。在这些情况下，概率会更高。如果您想知道正确的概率，您必须检查所有元素。在其他具有不同数字的测试用例中，任何随机元素将以 0.5 的概率位于有序列表的上半部分。

如果n是奇数，则随机数将具有此特征，概率 > 0.5。这是因为n/2-0.5元素小于中位数并且n/2+0.5元素 >= 中位数（在常见的测试用例中）。如果您希望 0.5 成为最小概率，您应该进行一些修改。我有一个没有证据的想法，如果它不起作用，也许有人会帮助我：从列表中选择 2 个随机值。较小的将是具有至少 0.5 概率的有效解决方案。