二分探索

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

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

大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。

n個のデータがある場合、時間計算量は<math>O(\log_2 n)</math>である（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なので「×」、位置1～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
結果	×	×	×	×	×	×	×	×	○	×

データが見つからない例(1)

下記のような配列から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より大きなデータのはずなので「×」。以上でデータが見つからないという結果になる。

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

データが見つからない例(2)

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

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

データの全体の一番右側が29より小さいので、データが見つからないという結果になる。

関連項目

• 二分法

（二分探索のようなアイデアで方程式の近似解を求める方法）ar:ديكوتومية