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

「バグ検出ドリル」の第6回で出題するのは「2分探索法」の問題です。ソフトウェア技術者の誰もが心得ておくべき常識的なアルゴリズムである2分探索法ですが、今回の問題では、いろんなところにバグがあります。問題文から、どこにバグがありそうか見つけ出してみよう！

[山浦恒央 東海大学 大学院 組込み技術研究科 非常勤講師（工学博士），MONOist]

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．自己採点シート

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

問題	内容	配点（点）
2分探索のプログラム	5分以上考えた	50
	ソート済みの配列を入力していない	20
	検索したい数値が見つからない場合、無限ループから抜け出せない	20
	上限、下限の配列要素の演算を間違えている	10
	上記以外のバグを見つけた	＋α
リスト3　自己採点シート

7．終わりに

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

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

参考文献

［1］「珠玉のプログラミング　本質を見抜いたアルゴリズムとデータ構造」（著：ジョン・ベントリー、翻訳：小林健一郎、2014、丸善出版）

［2］「C言語によるはじめてのアルゴリズム入門」（河西朝雄、2008、技術評論社）

【 筆者紹介 】

山浦 恒央（やまうら つねお）

東海大学 大学院 組込み技術研究科 非常勤講師（工学博士）

1977年、日立ソフトウェアエンジニアリングに入社、2006年より、東海大学情報理工学部ソフトウェア開発工学科助教授、2007年より、同大学大学院組込み技術研究科准教授、2016年より非常勤講師。

主な著書・訳書は、「Advances in Computers」 （Academic Press社、共著）、「ピープルウエア 第2版」「ソフトウェアテスト技法」「実践的プログラムテスト入門」「デスマーチ 第2版」「ソフトウエア開発プロフェッショナル」（以上、日経BP社、共訳）、「ソフトウエア開発 55の真実と10のウソ」「初めて学ぶソフトウエアメトリクス」（以上、日経BP社、翻訳）。