2分探索で値を検索

降順あるいは昇順で並べられたデータ配列から特定の値を探す方法に2分探索があります。

もちろん、はじめから順に探索する線形探索でもいいのですが、順に並べられているデータなら2分探索の方が速く検索できます。

ここでは、2分探索について解説していきます。

2分探索とは

2分探索は、名前の通りデータを2つに分けながら探索します。

例えば、

1,3,5,7,12,26,55,78

から56があるか調べる場合は、中間の12に着目します。

1,3,5,7,12,26,55,78

そして、56は12より大きいので12より右のデータにあることになります。

1,3,5,7,12,26,55,78

同様に、26,55,78の中間の55に着目します。

26,55,78

56は55より大きいので、右側に56はあることがわかります。

26,55,78

残るは78だけなので、56は存在しないことがわかります。

2分探索をコーディングする

ではプログラムで組んでいきます。

int nibun(int a[], int n, int target){
	int hajime=0;	//開始位置
	int owari=n-1;	//最終位置
	while(true){
		int center=(hajime+owari)/2;	//中間位置を取得
		if(a[center]==target){			//もし中間が目的値なら
			return center;				//中間位置を返す
		}else if(a[center]<target){		//もし目的値が上なら
			hajime=center+1;			//はじめを中心+1とする
		}else{
			owari=center-1;				//それ以外は最終位置を中心-1にする
		}
		if(owari==hajime){	//もし終わったら
			break;			//ループを抜ける
		}
	}
	return -1;
}

二分探索の計算量

では二分探索の計算量を計算します。

まず、線形探索の場合は、nこのデータに関して一つづつ調べるのでオーダーはnとなります。

一方、二分探索の場合は

  • 一回目のデータの長さ:n
  • 二回目のデータの長さ:n/2
  • 三回目のデータの長さ:n/4
  • 最終のデータの長さ:1

なので、t回実行して最終まで来たとするとざっくり

 n/2^{t}\approx1

が成り立ちます。よって、

 t\approx \log_{2}n

が得られます。オーダーは\log_{2}nだとわかります。線形探索のnよりオーダーが小さくなりますね。

著者:安井 真人(やすい まさと)