查找日志 n 时间中的概率排名

Question

给你一个序列a1，a2.....一个实数。我们想找到一个排名为大于 N/2。设计一个 O（log n） 算法，该算法将找到一个秩大于 n/2 的数字概率大于 1-1/n。注：1.数字未排序。

Answer 1

假设 n 是偶数。显而易见的事情是随机均匀地采样 lg n 元素并替换并返回最大值。最大值不在上半部分的概率是所有 lg n 样本都来自下半部分的概率。每个样本位于下半部分，概率为 1/2，因此失败概率为 （1/2）^（lg n） = 1/n。

Answer 2

这个问题的前提是这可以在 O（log n） 中完成。由于序列是无序的，您所能做的就是检查第一个 log n 个元素并返回最高的元素。

我不知道这是否真的返回一个高于 2/n 次的元素超过 1-1/n，但你没有要求数学证明，只是为了算法。

Python 伪代码：

max = None
for i in 0 to log(len(a)):
    if (max == None or a[i] > max:
         max = a[i]
return max