2

私が思うのは、二分探索には順番が必要だということです。私が間違っているか正しいかはわかりません。何かアドバイス？

4

7 に答える 7

4

ランダムな位置 (現在の部分の中央) にジャンプできる必要があるため、はい、ランダム アクセスが必要です。(また、要件は、コレクションが順序付けられていることです)。もちろん、構造がリスト/配列である場合はそうです。二分木であれば、明らかにランダム アクセスは必要ありません。

于 2012-04-10T20:24:18.683 に答える
4

ランダム アクセスなしでバイナリ検索を実行できます。たとえば、バイナリ ツリーはバイナリ検索をサポートしますが、ランダム アクセスはサポートしません (少なくともこの用語が通常使用されているように、コレクション内の任意の要素への一定の複雑さのアクセス)。

要素は、検索しているキーと比較できる順序である必要があります。これにより、キーがある値 X よりも大きい場合、それよりも小さい他のすべての要素よりも大きいと判断できます。 X (または、より大きいの代わりに less を使用できます)。

その関係は数値の順序付けに対応する必要はありませんが、1 つの要素のみとの比較に基づいて、要素の割合 (単一の要素だけでなく) を考慮から除外する機能を提供する必要があります。

于 2012-04-10T20:24:28.560 に答える
2

はい、ランダムアクセスが必要です。二分探索の全体的な考え方は、反復ごとに探索空間を半分に分割することであり、探索の新しい範囲を決定するためにインデックスが使用されます。中間点に到達するためだけに毎回検索空間をトラバースする必要がある場合は、アルゴリズムのポイントを否定することになります。

于 2012-04-10T20:25:59.637 に答える
2

はい。二分探索は、データ構造のすべての要素にランダム (非順次) にアクセスできる必要があります。

于 2012-04-10T20:24:43.383 に答える
1

検索が行われる前に並べ替える必要があります。昇順または降順で並べ替えることができます。これら 2 つの順序の違いは、探しているキーに基づいて、上半分または下半分で次に探す場所です。

int binary_search(int A[], int key, int imin, int imax)
{
  // test if array is empty
  if (imax < imin):
    // set is empty, so return value showing not found
    return KEY_NOT_FOUND;
  else
    {
      // calculate midpoint to cut set in half
      int imid = (imin + imax) / 2;

      // three-way comparison
      if (A[imid] > key):
        // key is in lower subset
        return binary_search(A, key, imin, imid-1);
      else if (A[imid] < key):
        // key is in upper subset
        return binary_search(A, key, imid+1, imax);
      else:
        // key has been found
        return imid;
    }
}

降順の配列がこのように二項演算子を反転する場合、これは昇順で機能します

// three-way comparison
          if (A[imid] < key):
            // key is in lower subset
            return binary_search(A, key, imin, imid-1);
          else if (A[imid] > key):
            // key is in upper subset
            return binary_search(A, key, imid+1, imax);
          else:
            // key has been found
            return imid;
        }
于 2012-04-10T20:25:59.203 に答える
1

二分探索は「真ん中に飛び込む」ことです。したがって、データに対する何らかの順序が必要であり (中間が適切に定義されるように) 、反復の代わりにインデックス付きアクセスが必要です (ジャンプできるようにするため、そうしないと O(log(CollectionSize)) のランタイムは実行されません)。可能）。

于 2012-04-10T20:24:23.120 に答える