algorithm - 不确定长度的数组

Question

如何在未知长度的排序数组中找到随机元素。

Answer 1

我假设你的意思how do I find if an element is part of the array?不是how do I return a random element from the array?。

使用二分搜索并假设长度非常大（您肯定有上限吗？）。如果您在每个步骤中选择的中间元素m超出了数组边界（您需要一种方法来说明这一点），则将搜索限制为索引小于m.

如果你没有办法判断一个元素是否在数组的边界之外，那么我看不出你如何解决这个问题。

Answer 2

我想你有一些可以循环的东西，但你不能事先确定长度。您可以通过循环项目获得一个随机项目，并计算该项目应该被选中的概率。

从（项目）中选择int（选定）的C# 示例：IEnumerable<int>

Random rnd = new Random();
int cnt = 0;
int selected = 0;
foreach (int item in items) {
  if (rnd.Next(++cnt) == 0) {
    selected = item;
  }
}

在第一个项目，你得到一个介于 0 和 0 之间的随机数，当然是 0，所以你保留那个项目。在第二个项目，你得到一个介于 0 和 1 之间的随机数，如果是 0，你保留第二个项目。依此类推，直到你的物品用完。对于每个额外的项目，保留该项目的概率会降低，这就是为什么最终得到集合中任何特定项目的概率是相同的。