2018年9月11日二分探索改良課題

昇順で整列されたデータから2分探索するプログラムを

降順のデータにした場合、どこを改良すればうまく動作するかを

検証してもらった。

まずは元のプログラムはこちら

/* 二分探索 */
#include <stdio.h>
#define MAX 10	/* データ件数 */

int main(void)
{
	/* 探索用データ */
	int n[] = {1, 5, 20, 55, 87, 100, 500, 1024, 2050, 8900};
	int i, key;			/* 探索回数カウント、探索キー */
	int low, high, mid;	/* 探索下限、中央値、探索上限 */
	
	/* 探索キーを入力 */
	printf("探索する値: ");
	scanf("%d", &key);
	
	/* 探索範囲（下限、上限）を設定 */
	low = 0;
	high = MAX-1;
	
	i = 1;
	while(1){
		/* 中央値を設定 */
		mid = (low + high) / 2;
	
		/* 探索処理 */
		if(key == n[mid]){		/* 一致 */
			printf("%d件目に見つかりました\n", mid+1);
			break;
		}
		else if(key < n[mid]){		/* 探索キーが中央値より下 */
			high = mid - 1;
		}
		else if(key > n[mid]){		/* 探索キーが中央値より上 */
			low = mid + 1;
		}
		
		/* 探索範囲がなくなった */
		if(low > high){
			printf("見つかりませんでした\n");
			break;
		}
		i++;	/* 探索回数のカウント */
	}
	/* 探索回数を表示 */
	printf("探索回数: %d回\n", i);
	
	return 0;
}

ボクは範囲を設定するための変数を変更したよ。

nakano.c

#include <stdio.h>
#define MAX 10

int main(void)
{
	int n[] = {10000,8200,6500,980,540,400,280,100,77,8};
	int i,key;
	int low,high,mid;
	
	printf("探索する値：");
	scanf("%d",&key);
	
	high = 0;
	low = MAX-1;
	
	i = 1;
	while(1){
		mid = (low + high) / 2;
		
		if(key == n[mid]){
			printf("%d件目に見つかりました\n",mid+1);
			break;
		}
		else if(key < n[mid]){
			high = mid + 1;
		}
		else if(key > n[mid]){
			low = mid - 1;
		}
		
		if(low < high){
			printf("見つかりませんでした\n");
			break;
		}
		i++;
	}
	
	printf("探索回数：%d回\n",i);
	
	return 0;
}

俺はif文の判定部分を見直してみた。

ishikawa.c

/* 二分探索 */
#include <stdio.h>
#define MAX 10	/* データ件数 */

int main(void)
{
	/* 探索用データ */
	int n[] = {10000,8200,6500,980,540,400,280,100,77,8};
	int i, key;				/* 探索回数カウント、探索キー */
	int low, high, mid;		/* 探索下限、中央値、探索上限 */
	
	/* 探索キーを入力 */
	printf("探索する値: ");
	scanf("%d", &key);
	
	/* 探索範囲（下限、上限）を設定 */
	low = 0;
	high = MAX-1;
	
	i = 1;
	while(1){
		/* 中央値を設定 */
		mid = (low + high) / 2;
		
		/* 探索処理 */
		if(key == n[mid]){		/* 一致 */
			printf("%d件目に見つかりました\n", mid+1);
			break;
		}
		else if(key > n[mid]){		/* 探索キーが中央より下 */
			high = mid - 1;
		}
		else if(key < n[mid]){		/* 探索キーが中央より上 */
			low = mid + 1;
		}
		
		/* 探索範囲がなくなった */
		if(low > high){
			printf("見つかりませんでした\n");
			break;
		}
		i++;		/* 探索回数のカウント */
	}
	
	/* 探索回数を表示 */
	printf("探索回数: %d回\n", i);
	
	return 0;
}