6

これはで説明されている問題Programming pearlsです。著者が説明した二分探索法がわかりません。誰かが詳しく説明するのを手伝ってもらえますか？ありがとう。

編集：私は一般的に二分探索を理解することができます。この特殊なケースで二分探索を適用する方法がわかりません。別の番号を選択できるように、欠落している番号が特定の範囲内にあるかどうかを判断する方法。英語は私の母国語ではありません。それが著者をよく理解できない理由の1つです。だから、平易な英語を使ってください:)

編集：あなたの素晴らしい答えとコメントをありがとうございました！この質問を解決することから私が学んだ最も重要な教訓は、バイナリ検索はソートされた配列だけでなく適用されるということです！

4

6 に答える 6

9

この Web サイトには、さらに詳しい情報があります。そこから引用：

「各整数を表す 20 ビットでこのバイナリ検索を表示すると便利です。アルゴリズムの最初のパスでは、(最大で) 100 万個の入力整数を読み取り、先行ゼロ ビットを含むものを 1 つのテープに書き込み、これらの 2 つのテープの 1 つには最大で 500,000 の整数が含まれているため、次にそのテープを現在の入力として使用し、プローブ プロセスを繰り返しますが、今回は 2 番目のビットで行います. 元の入力テープの場合N 個の要素が含まれている場合、最初のパスは N 個の整数を読み取り、2 回目のパスは最大で N/2、3 回目のパスは最大で N/4 というように読み取られるため、合計実行時間は N に比例します。不足している整数を見つけることができます。テープを並べ替えてからスキャンする方法ですが、それには N log N に比例する時間が必要です。」

ご覧のとおり、これは二分探索アルゴリズムのバリエーションです。問題を 2 つの部分に分割し、小さい部分の 1 つについて問題を解決します。

于 2009-10-29T09:44:20.090 に答える
2

一般的な考え方は次のとおりです。整数の範囲を選択し、その範囲内にあるすべての整数を選択します。整数の数が範囲のサイズよりも少ない場合、その範囲に1つ以上の欠落している数値が含まれていることがわかります。

これは、そもそもいくつかの欠落している数字があることをどのように知っているかという元の問題にも当てはまります。

于 2009-10-29T09:52:11.527 に答える
2

著者が得ようとしていることは、現在の整数範囲の中間点を選択し、2 つの出力ファイルを準備することだと思います。入力を読み取ると、中間点より上にあるものはすべて 1 つのファイルに入れられ、中間点より下にあるものはすべて別のファイルに入れられます。

それが終わったら、どちらか小さい方のファイルを選択し、新しい範囲として [lower bound, midpoint] または (midpoint, upper bound] を使用して、ファイルと範囲が十分に小さくなるまで操作を繰り返します。ビットマップ パターン (または出力ファイルの 1 つが空)。

ダミアン

于 2009-10-29T09:35:34.873 に答える
2

1 から N までの範囲の数値を考慮すると、それらの半分は N/2 より大きく、半分は N/2 より小さい

N/2 より大きいものは、MSB が 1 に設定されます。小さい方は MSB = 0 です。

セット全体を MSB に基づいて分割すると、2 つのセットが得られます: N/2 より小さい数値のセットと N/2 より大きい数値のセット

サイズが小さいパーティションには、欠落している要素があります。

次のステップでは、次の MSB を使用します。

  1. 小さい方のセットが N/2 未満の場合、それらの半分は N/4 未満 (2 番目の MSB=0) であり、残りの半分は N/4 よりも大きい (2 番目の MSB=1)。

  2. 小さい方のセットが N/2 より大きい場合、それらの半分は N/2+N/4 (2 番目の MSB=0) より小さく、残りの半分は N/2+N/4 (2 番目の MSB=1) より大きくなります。

各ラウンドは検索スペースを半分にし、それだけです。

 Sum ( N / 2^i ) for 0 <= i < log N gives you O(N)
于 2009-10-29T10:43:53.380 に答える
2

これは基本的にこの質問と同じ質問です。O(N) の複雑さを得るために十分なメモリの場合でも、同じアプローチがここで機能します。基本的に、すべての整数を正しい場所に再帰的に配置し、正しい値を持たないものを確認してください。

于 2009-10-29T10:51:27.773 に答える
1

それは、1 つを除いて 40 億の整数すべてを含むファイルについてです! それがこの場合の落とし穴です。

  1. 整数のリストに沿って移動しながら、合計を計算します。
  2. 最後に、数式 N * (N + 1) / 2 を使用して、すべての整数が存在するかのように合計を計算します。
  3. (2) で計算した合計から (1) の合計を抽出します。それが欠けている整数です。

例: 次のシーケンスがあるとします: 9 3 2 8 4 10 6 1 7 (1 から 10 で 5 が欠落している)。整数を順番に追加すると、9 + 3 + 2 + 8 + 4 + 10 + 6 + 1 + 7 = 50 になります。1 から 10 までのすべての整数の合計は、10 * (10 + 1) / 2 = 55 になります。 . したがって、欠けている整数は 55 - 50 = 5 です。

于 2009-10-29T09:35:32.267 に答える