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 です。したがって、その項目を保持します。2 番目の項目で 0 から 1 の間の乱数を取得し、それが 0 の場合は代わりに 2 番目の項目を保持します。アイテムがなくなるまで、など。追加のアイテムごとに、そのアイテムを保持する確率が低くなります。これが、コレクション内の特定のアイテムになる確率が同じである理由です。