二分探索について - imomoの勉強記録

今回は二分探索について復習したので、アルゴリズムや実装、注意点などを書いていこうと思います。

二分探索とは
アルゴリズム
二分探索の実装
- コード
- 実行
注意点とその理由
- 注意点1
- 注意点2
終わりに

二分探索とは

昇順にソートされた数列に対し、探索範囲を半分にしながらある値が存在するか探索するデータ探索アルゴリズムの一種です。

探索範囲が1/2,1/4…と半分になっていくので、計算量はO( $\log_{} N$ )となり高速な探索を行うことができます。

アルゴリズム

二分探索のアルゴリズムは以下の通りです。

探索範囲を配列全体とします。
探索範囲の中央の要素を調べます。
探索したい値(以下:key)と、中央の要素が一致すれば終了です。
3で一致しなかった場合

　　　・key < 中央の要素　の場合、探索範囲を左半分にして2に戻ります。
　　　・中央の要素 ≤ key　の場合、探索範囲を右半分にして2に戻ります。

二分探索の実装

C++で実装します。

コード

#include<iostream>
#include<vector>
#include<numeric>
using namespace std;

int binary_search(int key, vector<int>Sequence) {
	int  mid, cnt = 0,left = 0;
        int right = Sequence.size();    //※注意点1
	while (left < right) {
		cnt++;
		mid = (left + right) / 2;    //探索範囲の中央値をとる
		cout << "left:" << left << " right:" << right << " mid:" << mid << endl;
　　　　           //keyと中央の要素が等しかったら、探索回数を返す
		if (key == Sequence[mid]) {  
			return cnt;
                  //keyが中央の要素より小さかった場合探索範囲を左半分に絞る
		}else if(key < Sequence[mid]){  
			right = mid;
                 //keyが中央の要素以上だった場合探索範囲を右半分に絞る
		}else if(Sequence[mid] <= key){
			left = mid + 1;　　//※注意点2
		}
	}
	return -1;
}

int main(void) {
	int key,ans;
	cin >> key;
	vector<int>Sequence(100);
	iota(Sequence.begin(), Sequence.end(),0);
	ans = binary_search(key, Sequence);
	if(ans > 0) {
		cout << "keyの探索回数:" << ans << "回"<< endl;
	}else {
		cout << "keyは存在しないか対象範囲外です。" << endl;
	}
}

簡単にコードの解説をすると、

vectorとiotaで0~99の数列を用意
整数値(key)を入力して数列内を二分探索
keyが数列内に存在すれば探索にかかった回数、ない場合は-1を返す

となっています。

実行

適当な値を入れてみます。尚、最大探索回数ですが、計算量は( $\log_{} N$ )のため、7回となります。

・key = 35

left:0 right:100 mid:50
left:0 right:50 mid:25
left:26 right:50 mid:38
left:26 right:38 mid:32
left:33 right:38 mid:35
keyの探索回数:5回

midの値とSequence[mid]は同じにしてあります。
Sequence[mid]とkeyを比較し、keyが小さかったら左半分、大きかったら右半分に探索範囲を狭めていき、
Sequence[mid] == keyとなるか、left < rightが偽を返した(探索範囲がなくなった)場合探索終了となります。

・key = 86

left:0 right:100 mid:50
left:51 right:100 mid:75
left:76 right:100 mid:88
left:76 right:88 mid:82
left:83 right:88 mid:85
left:86 right:88 mid:87
left:86 right:87 mid:86
keyの探索回数:7回

・key = 1000

left:0 right:100 mid:50
left:51 right:100 mid:75
left:76 right:100 mid:88
left:89 right:100 mid:94
left:95 right:100 mid:97
left:98 right:100 mid:99
keyは存在しないか対象範囲外です。

left < rightが偽となり、探索範囲がなくなります。

注意点とその理由

注意点1

探索不可能になる恐れがある

探索範囲の右の値は、探索する配列の最大の添え字+1にする必要があります。
上記コードの場合、配列の添え字は0~99のため,right = 100が入っています。
理由として、midが添え字の最大値にならず、探索が不可能となるからです。

コード変更

検証をするため元のコードに変更を加えます。

int binary_search(int key, vector<int>Sequence) {
	int  mid, cnt = 0,left = 0;
        int right = Sequence.size() - 1; //※注意点1
	while (left < right) {
                 省略
	}
	return -1;
}

rightと配列の最大の添え字を同じにするため、-1をしています。

実行

探索範囲の最大値である key = 99で実行します。

left:0 right:99 mid:49
left:50 right:99 mid:74
left:75 right:99 mid:87
left:88 right:99 mid:93
left:94 right:99 mid:96
left:97 right:99 mid:98
keyは存在しないか対象範囲外です。

leftに99が代入されると探索する範囲がなくなり、探索終了となってしまいます。
そのため、rightは探索する配列の最大の添え字+1とする必要があります。

注意点2

無限ループが発生してしまう恐れがある

keyが中央の要素未満の場合、right = midでよいのですが、中央の要素以上だった場合にはleft = mid + 1
とする必要があります。
理由として、keyが探索範囲に存在しない場合、無限ループを起こしてしまうのを防ぐためです。

コード変更

検証をするため、元のコードに変更を加えます。

int main(void) {
	int key,ans;
	cin >> key;
	vector<int>Sequence(101);
	iota(Sequence.begin(), Sequence.end(),0);
	Sequence.erase(Sequence.begin() + key);
        省略
}

keyを除く0~100の数列としました。

}else if(Sequence[mid] <= key){
    left = mid;　　//※注意点2
}
if (cnt == 10)break;    //10回探索したら強制終了

また、加算処理を削除しました。
無限ループを止めるため、10回探索したら強制終了させるif文も追加してあります。

実行

key = 35で実行します。

left:0 right:100 mid:50
left:0 right:50 mid:25
left:25 right:50 mid:37
left:25 right:37 mid:31
left:31 right:37 mid:34
left:34 right:37 mid:35
left:34 right:35 mid:34
left:34 right:35 mid:34
left:34 right:35 mid:34
left:34 right:35 mid:34
keyは存在しないか対象範囲外です。

leftとrightの差が1のままであり、while文が終了しません。
このように、left及びrightの値が更新されず無限ループするため、keyが中央の要素以上の場合は1を足してあげる必要があります。

終わりに

調べながら実装してみて、注意点として挙げたミスにも引っ掛かり表面上でしか理解していなかったんだなと思いました。
C++には二分探索に便利なSTLも存在しており、このように長くコードを書く必要はないですが、復習を通して二分探索の仕組みについてより深く知れたので良かったです。