二分探索

出典: フリー百科事典『ウィキペディア（Wikipedia）』

二分探索（にぶんたんさく、BS;Binary Search）とは検索のアルゴリズムの一つ。二分検索、バイナリサーチともいう。

ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。

大小関係を用いるため、未ソートのリストや配列には二分探索を用いることはできない。

n個のデータがある場合、時間計算量は $O (log 2 n)$ である（O記法）。

n個のデータの中央の値を見ることで、1回の操作でn/2個程度（奇数の場合は(n-1)/2個、偶数の場合はn/2個または(n/2)-1個）の要素を無視することができる。

[編集] 例

具体例を示す。

[編集] データが見つかる例

下記のような配列から25を探しだすことを考える。なお、同一のデータは無いものとする。

位置	1	2	3	4	5	6	7	8	9	10
データ	1	3	5	11	12	13	17	22	25	28

結果欄を設け、目的のデータがあるか否か不明な部分を「？」、データを調べた上で目的のデータが無いとわかった部分を「×」、データを調べるまでもなく目的のデータが無い部分を「×」、目的のデータがあった部分を「○」にすることにする。検索前は、以下のようになる。

位置	1	2	3	4	5	6	7	8	9	10
データ	1	3	5	11	12	13	17	22	25	28
結果	?	?	?	?	?	?	?	?	?	?

まず、配列の中央の位置を求めると、(1+10)/2=5　

（端数は切捨、切上のどちらでもいいが、ここは切捨とする。以下同じ）

位置5のデータは12なので「×」、位置１～4まではデータを調べなくても「×」とわかる。目的のデータは位置6～10にあるかも知れない。

位置	1	2	3	4	5	6	7	8	9	10
データ	1	3	5	11	12	13	17	22	25	28
結果	×	×	×	×	×	?	?	?	?	?

位置6～10の中央の位置は、(6+10)/2=8

位置8のデータは22なので「×」、位置6～7までは「×」とわかる。目的のデータは位置9～10にあるかも知れない。

位置	1	2	3	4	5	6	7	8	9	10
データ	1	3	5	11	12	13	17	22	25	28
結果	×	×	×	×	×	×	×	×	?	?

位置9～10の中央の位置は、(9+10)/2=9

位置9のデータは25なので目的のデータが見つかったことになる。位置10は調べていないが、同一のデータは存在しないという想定なので「×」としてよい。

位置	1	2	3	4	5	6	7	8	9	10
データ	1	3	5	11	12	13	17	22	25	28
結果	×	×	×	×	×	×	×	×	○	×

[編集] データが見つからない例

下記のような配列から4を探しだすことを考える。なお、同一のデータは無いものとする。

位置	1	2	3	4	5	6	7	8	9	10
データ	1	3	5	11	12	13	17	22	25	28

まず、配列の中央の位置を求めると、(1+10)/2=5　

（端数は切捨、切上のどちらでもいいが、ここは切捨とする。以下同じ）

位置5のデータは12なので「×」、位置6～10まではデータを調べなくても「×」とわかる。目的のデータは位置1～4にあるかも知れない。

位置	1	2	3	4	5	6	7	8	9	10
データ	1	3	5	11	12	13	17	22	25	28
結果	?	?	?	?	×	×	×	×	×	×

位置1～4の中央の位置は、(1+4)/2=2

位置2のデータは3なので「×」、位置1も「×」とわかる。目的のデータは位置3～4にあるかも知れない。

位置	1	2	3	4	5	6	7	8	9	10
データ	1	3	5	11	12	13	17	22	25	28
結果	×	×	?	?	×	×	×	×	×	×

位置3～4の中央の位置は、(3+4)/2=3

位置3のデータは5なので「×」。もし、データ4が存在するならば、位置3のデータ5より小さいので左になるはずである。しかし、すでにそこには存在しないことがわかっている。また、位置3より右である位置4は、データを調べていないが、位置3より大きなデータのはずなので「×」。以上でデータが見つからないという結果になる。