-4

無限配列 (未知の配列長) が与えられ、この無限配列でソートされた n 個の整数要素があります。n (ソートされた要素の数) は不明です。log n 時間で、この無限配列内の整数 i の位置を見つけます。

4

2 に答える 2

4

log n は、バイナリ検索のように、配列が見つかるまで常に 2 で除算することを意味します... したがって、n の値を知る必要があります。

C# コード:

関数を呼び出すコード:

int position = findInteger(array, 0, searchedValue);

関数：

public int findInteger(int[] array, int position, int searchValue)
{
    if(array[position] = searchValue)
        return position;
    else if (array[position] > searchValue)
        position = position / 2;
    else // array[position] < searchValue
        position = (array.Count() + position)/2;
    findInteger(array, position, searchValue);
}
于 2012-09-20T16:34:00.203 に答える
2

問題の説明から、長さが不定の配列Aがあり、その少なくともn個のエントリが存在し、ソートされた順序になっているように見えます。最初のn個のエントリは昇順の正の整数であり、j> = nの場合、A[j]にアクセスするとnilが返されると想定します。最初は、nは不明です。iが与えられた場合、問題はA [j] == iとなるようにjを決定することです（または、そのようなものj<nが存在しない場合は、nilを返します）。

  1. k = 0、L=1に設定します。
  2. 真である間、ステップ3を実行します。
  3. k=LおよびL=2*Lに設定します。A [L]がnilの場合、ステップ4にブレークします。A[L]> iの場合、ステップ5にブレークします。それ以外の場合は続行します（ステップ2のwhileループ内）。
  4. 今k < n < L。A [k：L]で二分探索を実行して、最後の非nilエントリA[n-1]を見つけます。L=n-1に設定します。次に、ステップ5に進みます。
  5. ここで、A [L]>=iです。A [k：L]で二分探索を実行して、iを見つけます。見つかった場合はそのインデックスを返し、見つからなかった場合はnilを返します。

述べられたメソッドがO（ln n）有界であること2*lg(n)を確認するために、n（またはA [L]> iとなるようなL）を見つけるために最大のステップを使用し、次にlg(n)A[kでiを見つけるために最大のステップを使用することに注意してください。 ：L]、ここでlg（n）= ln（n）/ ln（2）。

j> = nのときにA[j]にアクセスしてもnilが返されないと仮定すると、代わりに「乱数」が返されます。このアプローチは失敗します。一つには、A [j] == iが見つかるかもしれませんが、j> n; もう1つは、O（ln n）の時間制限が成立しないか、確率的にのみ成立する場合があります。A [L]値シーケンスの減少を検出するには、アルゴリズムを修正し直す必要があります。また、AがA [n + 1]> A [n]> A [n-1]である場合、nはとにかく決定できません。

于 2012-09-20T17:22:46.490 に答える