連載
» 2018年05月14日 10時00分 公開

山浦恒央の“くみこみ”な話(106):バグ検出ドリル(6)いろんなところにバグがいる! 2分探索法の問題 (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分探索のプログラム

Copyright © ITmedia, Inc. All Rights Reserved.