これは、テクニックを説明するための簡単なCソリューションです。面倒なファイルI/Oの詳細を抽象化するために、次の3つの関数の存在を想定しています。
unsigned long next_number (void)ファイルから数値を読み取り、それを返します。再度呼び出されると、ファイル内の次の番号が返されます。ファイルの終わりに遭遇したときの動作は未定義です。
int numbers_left (void)を使用して読み取ることができる数値がさらにある場合はtrue値を返し、next_number()ファイルの終わりに達した場合はfalseを返します。
void return_to_start (void)読み取り位置をファイルの先頭に巻き戻し、次の呼び出しでnext_number()ファイルの最初の番号が返されるようにします。
unsigned longまた、ANSI C実装に準拠するために必要な、少なくとも32ビット幅であると想定しています。現代のCプログラマーは、代わりにuint32_tfromを使用することを好むかもしれませんstdint.h。
これらの仮定を前提として、解決策は次のとおりです。
unsigned long count_numbers_in_range (unsigned long min, unsigned long max) {
unsigned long count = 0;
return_to_start();
while ( numbers_left() ) {
unsigned long num = next_number();
if ( num >= min && num <= max ) {
count++;
}
}
return count;
}
unsigned long find_missing_number (void) {
unsigned long min = 0, max = 0xFFFFFFFF;
while ( min < max ) {
unsigned long midpoint = min + (max - min) / 2;
unsigned long count = count_numbers_in_range( min, midpoint );
if ( count < midpoint - min + 1 ) {
max = midpoint; // at least one missing number below midpoint
} else {
min = midpoint; // no missing numbers below midpoint, must be above
}
}
return min;
}
注意すべき詳細の1つは、とmin + (max - min) / 2の平均を計算する安全な方法です。一見単純なように中間値がオーバーフローするため、偽の結果は生成されません。minmax(min + max) / 2
また、再帰を使用してこの問題を解決したくなる場合でも、2つの理由から、代わりに反復ソリューションを選択しました。1つは、実際に行われていることを（おそらく）より明確に示すためです。2つ目は、タスクがメモリを最小限に抑えることであったためです。おそらくスタックも含まれている使用。
最後に、このコードを最適化するのは簡単です。たとえば、countゼロに等しくなるとすぐに戻る、1回のパスで範囲の両方の半分の数を数え、欠落している数が多い方を選択する、またはバイナリ検索をパスの数を減らすために、いくつかのn >2をn- ary検索します。ただし、サンプルコードをできるだけ単純にするために、このような最適化は行わないでおきます。必要に応じて、たとえば、現在の32ではなくファイルを最大8回パスするようにコードを変更してみてください（ヒント：16要素の配列を使用してください）。