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

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

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

4．今回の問題

　今回は、2分探索法のプログラムを示します（リスト2）。このプログラムは、main関数で静的な配列arrayを定義し、binary_search関数に、検索する配列（array）、検索する数値（target）、配列の要素数（index_size）を入力すると、検索する数値が何番目の配列に入っているか出力するものです。

　このプログラムのバグを見つけてください（バグは1つだけではありません）。なお、本問題の制限事項は、以下の通りです。

• 検索する値（変数target）は、コンソールからint型で取れる範囲内を入力する
• 配列arrayは、int型で静的に定義する
• コードの可読性、実行速度は考慮しない

　数分見ても分からない場合、デバッガを使って、チャレンジしてみてください。

#include <stdio.h>
int binary_search(int array[], int target, int index_size){
	// low: 下限, high: 上限, mid: 中央値
	int low = 0, high = index_size - 1, mid = 0;
	
	while (1) {
		mid = low + ( (high - low) / 2);
		if (array[mid] == target) {
			return mid;
		} else if (array[mid] > target){
			high = mid + 1;
		} else {
			low = mid - 1;
		}
	}
	return -1;
}
int main(void)
{
	//入力する配列array
	int array[] = {7, 3, 5, 20, 1, 12, 15, 16, 4};
	int index_size = 0;		//配列の要素数
	int target;				//検索する数値
	int result = 0;			//場所
	index_size = sizeof(array) / sizeof(array[0]);
	printf("検索する値を入力してください\n");
	scanf("%d",&target);
	result = binary_search(array, target, index_size);
	if (result == -1){
		printf("%dはありません.\n", target);
	} else {
		printf("場所は%d番目です.\n", result);
	}
	return 0;

リスト2　2分探索のプログラム