バグ検出ドリル（6）いろんなところにバグがいる！ 2分探索法の問題：山浦恒央の“くみこみ”な話（106）（4/4 ページ）

5．解答

　今回のバグは、以下の通りです。

• ソート済みの配列を入力していない
• 検索したい数値が見つからない場合、無限ループから抜け出せない
• 右側、左側の配列の演算を間違えている

5.1　ソート済みの配列を入力していない

　2分探索法は、ソート済みの配列に対して有効な手法です。このプログラムの配列arrayには、ソートしてある数値が入っておらず、検索する数値によってはプログラムが正常終了しない可能性があります。使用上の注意をあらかじめ押さえておきましょう。解決策は、以下のように、あらかじめソート済みの配列を定義することです。例えば、以下です。

int array[] = {1, 3, 5, 8, 10, 12, 15, 16, 17};

5.2　検索したい数値が見つからない場合、無限ループから抜け出せない

　上記の4.1で説明した配列を定義しても、全ての問題は解決しません。5行目をご覧ください。このプログラムで配列の検索処理は、5行目の無限ループ内で実施し、検索したい数値が見つかったら終了します。よく見ると、検索したい数値が見つからない場合の処理を記述していません。例えば、検索したい値を示した変数targetに対して、30などの数値を入力すると、プログラムが終了しません。

　解決策は、検索したい値が見つからない場合の終了条件を、例えば、以下のように記述することです。

while (low <= high) {

　上の例は、「下限の配列要素≦上限の配列要素となった場合は、ループから抜ける」という記述です。これで、無限ループは解消できますね。

5.3　右側、左側の配列の演算を間違えている

　上記の4.2のバグを修正しても、もう１つバグがあります。以下の記述を見てください。

} else if (array[mid] > target){
	high = mid + 1;
} else {
	low = mid - 1;
}

　「中間値の値＞検索する値」の場合、「上限＝中間値−1」としないと（1つ内側に入り込まないと）、効率良く探索できません。また、else文の「中間値の値＜検索する値」の場合は、「下限＝中間値＋1」とすべきです。正しい記述は、下記となります。

} else if (array[mid] > target){
	high = mid - 1;
} else {
	low = mid + 1;
}

6．自己採点シート

　今回の自己採点シートを示します。他にもバグはあるかと思います。合わせて探してみてください。

7．終わりに

　ソフトウェアのバグは、プログラムのあらゆる箇所に潜んでおり、バグがあると分からずに使っていることも少なくありません。今回出題した2分探索法も、そんなプログラムの1つです。Texの開発者として有名なアルゴリズムの大家、ドナルド・クヌース先生（ことしで80歳です！）によると、「最初に2分探索法の考え方が公開されたのが1946年だったのに、バグなしのプログラムが出版されたのは1962年になってからだった」そうです^［1］。

　短いプログラムでも、「バグなく作るというのは難しい」と感じる問題でした。皆さんが携わっているプログラムにも必ずどこかにバグがあるでしょう。あらゆる可能性を考察してみてください。