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

[山浦恒央 東海大学 大学院 組込み技術研究科 非常勤講師（工学博士），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分探索のプログラム