これがどのように機能するのか理解できないようです。
質問:
最大 40 億の 32 ビット整数をランダムな順序で含むシーケンシャル ファイルが与えられた場合、ファイルにない 32 ビット整数を見つけます (少なくとも 1 つ欠落している必要があります)。
答え:
この二分探索を、各整数を表す 32 ビットで見ると役に立ちます。アルゴリズムの最初のパスでは、(最大で) 40 億個の入力整数を読み取り、先頭の 0 ビットを持つものを 1 つの順次ファイルに書き込み、先頭の 1 ビットを持つものを別のファイルに書き込みます。
これらのファイルの 1 つには最大で 20 億の整数が含まれているため、次にそのファイルを現在の入力として使用し、プローブ プロセスを繰り返しますが、今回は 2 番目のビットで行います。
では、ファイルを何度も分割する (バイナリ検索) ことで、実際にどのようにして 32 ビット整数が見つからないのでしょうか?
各パスの後、次のパスは、コンパイルした 2 つのリストの小さい方になります。
ある時点で、空のリストに遭遇する必要があり、これにより番号が決定されます。たとえば、3 ビットの数値を使用してみましょう。
000
001
110
100
111
最初のパスの後
000
001
110
100
111
次に、最初のリストの 2 番目のビットを調べます。これは、2 番目のビットよりも小さい (または等しい) ためです。それらをに分割します
000
001
empty list
で始まるファイルが空であることに注意してください。これは、 soで始まり、欠落01している数字がないことを意味します。01010011
最終的に欠落したリストが必要になる理由は、次のパスで毎回小さいリストを選択しているためです。
最終的に、分割を続けると、(最大で) 40 億個のファイルができ、それぞれに 1 つの整数が含まれます。理論的には、ファイルがないため、どれが欠けているかを「知る」ことができます。
また、整数の数が奇数になる場合もあります。その場合、小さい方の半分の数字が欠落します。これにより、欠落している番号を簡単に見つけることができます。
偶数の場合、2 つが欠けていることがわかります。この場合、それぞれの半分よりも小さいパーツを見つけてから、上記のソリューションに進む必要があります。