>> C言語入門トップに戻る

二分探索

今回は二分探索について説明します。
二分探索とは、前もってソートされた配列の中から、
中央の値と目的の値を比較して、目的の値が前方にあるのか後方にあるのかを判断して
検索していく方法です。
最初に中央の値と比較して、前方か後方かだけへの検索を繰り返していくので、
一つ一つ見て行く線形探索より高速です。

下記のコードを見てください。

#include <stdio.h>
//目的値
#define FIGURE 7

int main(void)
{
	//前もってソートしておく
	int test[10]={1,2,3,4,5,6,7,8,9,10};

	//配列の要素数を取得
	int number=sizeof(test)/sizeof(int);
	//最小の添字
	int min=0;
	//最大の添字
	int max=number-1;
	//中央の要素番号
	int mid;

	//最大値と最小値が一致するまでループ
	while(min<=max){

		mid=(min+max)/2;

		//まず一致するか比較
		if(test[mid]==FIGURE){
			printf("見つかりました\n");
			return 0;
		}else if(test[mid]<FIGURE){
			//目的値が中央値よりも上なら、最小値を中央値の一つ上に設定
			min=mid+1;
			
		}else if(test[mid]>FIGURE){
			//目的値が中央値よりも下なら、最大値を中央値の一つ下に設定
			max=mid-1;
		}
	}

	printf("見つかりませんでした\n");

	return 0;
}

これを実行すると「見つかりました」と表示されます。

まず中央値を調べるために、添字の最小値と最大値を足して２で割り、中央の添字を求めてます。
この値とまず一致するか調べ、一致しなければ、目的値が中央値より大きいのか小さいのか調べます。
目的値の方が大きければ添字の最小値を中央値の添字より1つ上に設定します。
逆に目的値の方が小さければ添字の最大値を中央値の添字より1つ下に設定します。
次のループで、最小値・最大値が更新されてるので、次の新しい中央値を求められるというわけです。
もし目的の値がなければ、最小値が最大値以上になるか、最大値が最小値以下になるかのどちらかになるので、
その場合はループを終了します。
毎回その最大値or最大値を更新してるところがポイントですね。

以上が二分探索の説明になります。

次回は線形リストについて説明します。


>> 【線形リスト】に進む
>> C言語入門トップに戻る